2017电大计算机考试题
一、选择题
1.下列程序段的时间复杂度为( )。
i=0，s=0; while (s
(A) O(n1/2) (B) O(n1/3) (C) O(n) (D) O(n^2)
2.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列( )存储方式最节省运算时间。
(A) 单向链表 (B) 单向循环链表 (C) 双向链表 (D) 双向循环链表
3.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。
(A) s->next=p->next;p->next=-s;
(B) q->next=s; s->next=p;
(C) p->next=s->next;s->next=p;
(D) p->next=s;s->next=q;
4.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。
(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1 (C) 3，1，2，5，4，6 (D) 1，5，4，6，2，3
5.设有一个10阶的下三角矩阵A(包括对角线)，按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为( )。
(A) 10 (B) 19 (C) 28 (D) 55
6.设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，，Nm个度数为m的结点，则该树中共有( )个叶子结点。
7. 二叉排序树中左子树上所有结点的值均( )根结点的.值。
(A) < (B) > (C) = (D) !=
8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( )。
(A) 129 (B) 219 (C) 189 (D) 229
9. 设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。
(A) n2(B) n(n+1) (C) n(n+1)/2 (D) n(n-1)/2
10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有( )个结点。
(A) 2n (B) n+l (C) 2n-1 (D) 2n+l
11.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。
(A) 6 (B) 7 (C) 8 (D) 9
12.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。
(A) F，H，C，D，P，A，M，Q，R，S，Y，X
(B) P，A，C，S，Q，D，F，X，R，H，M，Y
(C) A，D，C，R，F，Q，M，S，Y，P，H，X
(D) H，C，Q，P，A，M，S，R，D，F，X，Y
13、设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过( )次比较。
(A) 1 (B) 2 (C) 3 (D) 4
14、设指针变量p指向双向链表中结点A，指针变量s指向插入的结点X，则在结点A的后面插入结点X的操作序列为( )。
(A) p->right=s; s->left=p; p->right->left=s; s->right=p->right;
(B)s->left=p;s->right=p->righ;p->right=s; p->right->left=s;
(C) p->right=s; p->right->left=s; s->left=p; s->right=p->right;
(D) s->left=p;s->right=p->right;p->right->left=s; p->right=s;
15、下列各种排序算法中平均时间复杂度为O(n2)是( )。
(A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 冒泡排序
16.进程的三个基本状态在一定条件下可以相互转化，进程由就绪状态变为运行状态的条件是 () 。
(B)A.时间片用完 B.等待某事件发生
(C)C.等待的某事件已发生 D.被进程调度程序选中
17.进程的三个基本状态在一定条件下可以相互转化，进程由运行状态变为阻塞状态的条件是 () 。
(D)A.时间片用完 B.等待某事件发生
(E)C.等待的某事件已发生 D.被进程调度程序选中
18.下列的进程状态变化中， () 变化是不可能发生的。
A.运行à就绪 B.就绪à运行 C.等待à运行 D.等待à就绪
19.一个运行的进程用完了分配给它的时间片后，它的状态变为 () 。
A.就绪 B.等待 C.运行 D.由用户自己确定
20.用V操作唤醒一个等待进程时，被唤醒进程的状态变为 () 。
A.等待 B.就绪 C.运行 D.完成
二：综合题
1、下图所示的森林：
(1) 求树(a)的先根序列和后根序列;
(2) 求森林先序序列和中序序列;
(3)将此森林转换为相应的二叉树;
2、设散列表的地址范围是[ 0..9 ]，散列函数为H(key)= (key^2+2)MOD 9,并采用链
表处理冲突，请画出元素7、4、5、3、6、2、8、9依次插入散列表的存储结构。
3、已知数据六个字母及在通信中出现频率如下表：
把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。
(1) 画出对应的Huffman树。
(2)计算带权路径长度WPL。
(3) 求A、B、C、D、E、F的Huffman编码。
4、已知有如下的有向网：
求顶点A到其它各顶点的最短路径(采用Dijkstra算法，要有过程)。
5、编写算法，实现带头结点单链表的逆置算法
void invent(Lnode *head) {Lnode *p,*q; if(!head->next) return ERROR; p=head->next; q=p->next; p->next =NULL; while(q) {p=q; q=q->next; p->next=head->next; head->next=p;} }
6、设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
void Insert_sq(Sqlist va[], ElemType x) {int i, j, n; n=length(va[]); if(x>=va[i]) va[n]=x; else {i=0; while(x>va[i]) i++; for(j=n-1;j>=I;j--) va[j+1]=va[j]; va[i]=x; } n++; }
7、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算法，删除表中所有大于x且小于y的元素(若表中存在这样的元素)同时释放被删除结点空间。
void Delete_list(Lnode *head, ElemType x, ElemType y) {Lnode *p, *q; if(!head) return ERROR; p=head; q=p; while(!p) {if(p->data>x) && (p->datanext; free(p); p=head; q=p; } else {q->next=p->next; free(p); p=q->next; } else {q=p; p=p->next; } } }
8、对于一个栈，给出输入项A,B,C,D，如果输入项序列为A,B,C,D，试给出全部可能的输出序列。
9、AOE网G如下所示，求关键路径。(要求标明每个顶点的最早发生时间和最迟发生时间，并画出关键路径)
10、请用信号量实现对某数据库的读者-写者互斥。 要求：(1)读者与写者之间互斥，写者与写者之间互斥。 (2)读者之间不互斥。
【2017电大计算机考试题】相关文章：