四川大学期末考试试题开卷2018——2019学年第1学期A卷

（2018——2019学年第 1 学期） A卷

课程号： 课序号： 课程名称：计算机软件技术基础I 任课教师： 成绩：

适用专业年级：自动化2017级 学生人数：114 印题份数：120 学号： 姓名：

考 生 承 诺

我已认真阅读并知晓《四川大学考场规则》和《四川大学本科学生考试违纪作弊处分规定（修订）》，郑重承诺：

1、已按要求将考试禁止携带的文具用品或与考试有关的物品放置在指定地点；

2、不带手机进入考场；

3、考试期间遵守以上两项规定，若有违规行为，同意按照有关条款接受处理。

试卷编号：

8. 设有如下的单链表的按序号查找的算法，其时间复杂度为（ ）。

LinkNode *GetNode(Linklist head, int i)

{

int j;

ListNode *p;

P = head; j=0;

while(p->next && j

9. 假定一个链式队列的队首和队尾指针分别用front和rear表示，每个结点的结构为：，当出列时所进行的指针操作为（ ）

A. front = front->next; B. rear = rear->next;

C. front->next = rear; rear = rear->next;

D. front = front->next; front->next = rear;

10. 如果进栈序列为e1,e2,e3,e4，则可能的出栈序列是（ ）。

A. e3，e1，e4，e2 B. e2，e4，e3，e1 C. e3，e4，e1，e2 D. 以上均有可能

11. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。

A. 1和5 B. 2和4 C. 4和2 D. 5和1

12. 判断一个顺序栈ST（最多元素为mo）为空的条件是（ ）。

A. ST->top <> 0 B. ST->top == 0 C. st->top <> mo D. st->top == mo

13. 有一个N×N的下三角矩阵A，若采用行优先进行顺序存储，每个元素占用k个字节，则Aij(1≤i≤N,1≤j≤i)元素的相对字节地址（相对首元素地址而言）为（ ）

A. (i×(i+1)/2+j-1)×4 B. (i×i/2+j)×4

C. (i×(i-1)/2+j-1)×4 D. (i×(i-1)/2+j)×4

14. 一个数组元素a[i]与（ ）的表示等价。

A. &a + i B. *(a + i) C. *a + i D. a + i

15. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，行下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素（ ）的起始地址相同。

A. M[2][4] B. M[3][4] C. M[3][5] D. M[4][4]

16. 对一棵完全二叉树，按从上至下、从左至右的方式从1开始进行编号。若编号为i的结点存在左孩子，则左孩子结点的编号为（ ）。

A. 2i B. 2i-1 C. 2i+1 D. 2i+2

17. 利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（ ）

A. 29 B. 38 C. 55 D. 58

18. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

19. 线索二叉树是一种（ ）结构。

A. 逻辑 B. 逻辑和存储图 C. 物理

试卷编号：

20. 设高度为h的二叉树上只有度为0或度为2的结点，则此类二叉树中所包含的结点数至少为（ ）。

A. 2h B. 2h-1 C. 2h+1 D. h

21. 对于长度为9的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度为（ ）的值除以9。

A. 18 B. 20 C. 22 D. 25

22. 对线性表进行二分查找时，要求线性表必须（ ）。

A. 以顺序方式存储 B. 以顺序方式存储，且结点按关键字有序排序

C. 以链接方式存储 D. 以链接方式存储，且结点按关键字有序排序

23. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为（ ）。

A. n B. n + 1 C. (n - 1)/2 D. (n + 1)/2

24. 链表适用于（ ）查找。

A. 顺序 B. 二分法 C. 顺序，也能二分法 D. 随机

25. 一组记录的关键码为（46，24，57，23，40，15），则利用选择排序的方法，第二趟排序的结果是（ ）。

A. 15，46，57，24，40，23 B. 15，23，57，46，40，24

C. 15，23，24，46，40，57 D. 15，23，24，40，46，57

26. 从未排序的序列中依次取出元素与已排序序列中的元素进行比较，然后将其放在排序序列的合适位置，该排序方法称为（ ）排序法。

A. 选择 B. 希尔 C. 插入 D. 冒泡

27. 以下结点序列是堆的为（ ）。

A. 100,90,80,60,85,75,20,25,10,70,65,50

B. 100,70,50,20,90,75,60,25,10,85,65,80

C. 100,80,90,60,85,75,20,25,10,70,65,50

D. 100,50,70,20,90,75,60,25,10,85,65,80

28. 下列关键字序列中，（ ）是堆。

A. 16, 72, 31, 23, 94, 53 B. 94, 23, 31, 72, 16, 53

C. 16, 53, 23, 94，31, 72 D. 16, 23, 53, 31, 94, 72

29. 工业过程控制系统中，运行的操作系统最好是（ ）。

A. 分时系统 B. 实时系统 C. 分布式操作系统 D. 网络操作系统

30. 现代操作系统的两个基本特征是（ ）和资源共享。

A. 多道程序设计 B. 中断处理 C. 程序的并发执行 D. 实现分时与实时处理

31. 在下列操作系统中强调并行性的操作系统是（ ）

A. 分时系统 B. 实时系统 C. 分布式操作系统 D. 网络操作系统

32. 在任何时刻，一个进程的状态变化（ ）引起另一个进程的状态变化。

A. 必定 B. 一定不 C. 不一定 D. 不可能

33. 引入多道程序的目的是（ ）。

A. 提高实时响应速度 B. 增强系统交互能力

C. 为了充分利用主存储器 D. 充分利用CPU，减少CPU等待时间

34. V操作词V(S)，S为一信号量，执行V操作时完成以下操作：S=S+1;若S>0，则继续执行；若S

A. 将进程阻塞，插入等待队列 B. 将队列中的一个进程移出，使之处于运行状态

C. 将进程变为挂起状态 D

试卷编号：

35. 在单一处理器上，将执行时间有重叠的几个程序称为（ ）。

A. 顺序程序 B. 多道程序 C. 并发程序 D. 并行程序

36. 进程间的基本关系为（ ）。

A. 相互与相互制约 B. 同步与互斥

C. 并行执行与资源共享 D. 信息传递与信息缓冲

37. 分页式存储管理的主要特点是（ ）

A. 不要求作业同时全部装入主存 B. 不要求作业装入到主存的连续区域

C. 要求扩充主存容量 D. 要求处理缺页中断

38. 页式存储管理中，页表的大小由（ ）决定。

A. 作业所占页的多少 B. 计算机编址范围 C. 操作系统 D. 系统统一指定

39. 可由CPU调用执行的程序所对应的地址空间为（ ）。

A. 名称空间 B. 虚拟地址空间 C. 相对地址空间 D. 物理地址空间

40. 若处理器有32位地址，则它的虚拟地址空间为（ ）字节。

A. 2GB B. 4GB C. 100KB D. 0KB

二、 编程题（20分）

分别编写在非递减有序顺序表和带头结点的非递减有序单链表上统计出值界于x、y（要求x不超过y）之间的元素个数的函数，统计结果由函数值返回。分析函数的时间复杂度和空间复杂度。

假设，顺序表的数据结构为：

const int MAXSIZE=100;

struct SequenList

{

int data[MAXSIZE];

int length;

};

链表的数据结构为：

struct LNode

{

int data; // 数据域

LNode* next; // 指针域

};

typedef LNode* LinkList;

试卷编号：

三、 程序设计题（20分）

下面定义的大数类型中假设构造函数、赋值运算符和输出函数均已正确定义，其中大数赋值运算符和输出函数的实现如下所示。

class BigNum{

private:

int radix=10000; // 进制，默认为10000

int data[2000]; // 存储大数的整型数组，从下标0开始，每个下标元素存储5位整数

int len; // 大数长度，即data[0]至data[len-1]中存储有数据

/* data[0]至data[len-1]由低位向高位进行存储，如大数321，将存储为

data

public:

BigNum(const char*); // 将一个字符串类型的变量转化为大数

BigNum & operator=(const BigNum &); //重载赋值运算符，大数之间进行赋值运算

BigNum add(const BigNum &) // 两个大数相加

BigNum mul(const BigNum &) // 两个大数相乘

void print(); // 输出大数

};

void BigNum::print() //输出大数

{

int i;

for(i = len - 1 ; i >= 0 ; i--)

{

cout << a[i];

}

cout << endl;

}

BigNum &BigNum::operator=(const BigNum &n)

{ // 重载赋值运算符，大数之间进行赋值运算

len = n.len;

memset(data,0,sizeof(data)); // data数组所有元素均置为0

for(int i = 0 ; i < len ; i++)

a[i] = n.a[i];

return *this; // 返回当前大数对象的指针

}

我们可以使用BigNum a=new BigNum("321");定义大数并赋初值；使用BigNum b; b=a;对大数赋值；使用a.print();输出大数a。

请为类BigNum编写成员函数add和mul，然后利用它们需要编写程序，求9a80f2aa0f243354aad1485001f5fd05.png的值，要求n由键盘输入，n的允许范围为1≤n≤1000，必须在程序中进行判断

试卷编号：