发布时间 : 星期一 文章软件技术基础总复习题及参考答案更新完毕开始阅读71408392fe4733687f21aa38
软件技术基础 总复习题及参考答案
一、 选择题
1、 线性表若是采用链式存储结构时，要求内存中可用存储单元的地址 D 。 A、必
须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以 2、 栈和队列都是 B 。
A、顺序存贮的线性结构 B、限制存取点的线性结构 C、链接存贮的线性结构 D、限制存取点的非线性结构 3、 与线性表的链接存贮不相符合的特性是 C 。 A、
便于插、删运算 B、存贮空间动态分配 C、需要连续的存贮空间 D、只能顺序查找
4、 设二叉树的根为第一层，则第 i 层上的结点数最多有 B 。
A、２
i B、２i +1 D、２
i -1C、２-１ i 5、 如将一棵有 n 个结点的完全二叉树按顺序存放方式，存放在下标编号为 0, 1,…, n-1
的一维数组中，设某结点下标为 k(k>0)，则其双亲结点的下标是 A 。 A、(k-1)/2 B、(k+1)/2
C、k/2 D、k-1
6、 由权值分别为 3,8,6,2,5 的叶子结点生成一棵霍夫曼树，它的带权路径长度为
A 。 A、53 B、48 C、72 D、24 7、 设 I 和 O 分别表示入栈和出栈操作，栈的初态和终态都为空，则下列操作序列 合
法的有_ D_ _。
A、IOIOOIOI B、IOOIOIIO C、IIIOIOIOO D、IIOIIOOO
8、 二叉树的前序序列为 EFHIGJK，中序序列为 HFIEJKG，则二叉树的根为 C 。
A、K B、G C、E D、H
9、 对有序表{ -1, 0, 1, 3, 4, 6, 8, 10, 12 }进行折半查找，则查找 12 需要 比较的次数
为 B 。 A、3 B、4 C、5 D、6 10、 在一个单链表中，若 q 结点是 p 结点的前驱结点，若在 q 与 p 之间插入结点 s， 则执
行 D 。
A、s→link = p→link; p→link = s; B、p→link = s; s→link = q; C、p→link = s→link; s→link = p; D、q→link = s; s→link = p;
11、 一个栈的入栈序列为 a，b，c，则出栈序列不可能的是 C 。 A、
c,b,a B、b,a,c
C、c,a,b D、a,c,b
12、 如果将一棵有 n 个结点的完全二叉树按层次遍历次序，存放在下标编号为 0,
1, … , n-1 的一维数组中，设某结点下标为 k( k ? 0 )，如果其左孩子存在， 则其左孩子结点的下标是 C 。
A、2k– 1 B、2k C、2k + 1 D、2k + 2 13、 用整数 5, 7, 3, 6, 4 作为五个树叶的权值，可以构造一棵带权路径长度值为
C 的霍夫曼树。
A、78 B、62 C、57 D、25
14、 设单链表中结点结构为(data,link)，若想删除结点*p 的直接后继，则应执行 下
列哪一个操作 A 。
A、p->link=p->link->link; B、p=p->link; p->link=p->link->link; C、p->link=p->link; D、p=p->link->link;
15、 顺序表是线性表的 B 。 A、链式存储结构 B、顺序存
储结构
C、索引存储结构 D、散列存储结构 16、 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采
用 A 存储方式最节省时间。
A、顺序表 B、单链表 C、双链表 D、单循环链表 17、 当利用大小为 n 的数组顺序存储一个栈时，假定用 top= =n 表示栈空，则向这 个栈插
入一个元素时，首先应执行 B 语句修改 top 指针。 A、top++; B、top--; C、top=0; D、top; 18、 对于任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点为 n2.,则 A
A、n0= n2+1 B、n2= n0+1
C、n0= 2n2+1 D、n2=2n0+1 19、 具有 35 个结点的完全二叉树的深度为 A 。
A、5 B、6
C、7 D、8 20、 在有向图中，所有顶点的入度之和是所有顶点出度之和的 B 倍。
A、0.5 B、1 C、2 D、4 21、 若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，
41，24）从小到大进行排序，共要进行 B 次比较。 A、33 B、45 C、70 D、91
22、 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序 列均相同。
A、0 B、1
C、2 D、不存在这样的二叉树
23、 数据结构是一门研究非数值计算的程序设计问题中计算机的 A 以及它
们之间的 B 和运算等的学科。 ① A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 ② A.结构 B.关系 C.运算 D.算法 24、 数据结构在计算机内存中的表示是指 A 。
A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 25、 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。
A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法
26、 在数据结构中，从逻辑上可以把数据结构分成 C 。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构
C.线性结构和非线性结构 D.内部结构和外部结构 27、 带头结点的单链表 head 为空的判定条件是 B 。
A. head= =NULL B. head->next= =NULL
C. head->next= =head D. head !＝ NULL 28、 在循环双链表的 p 所指结点之前插入 s 所指结点的操作是 D 。
A. p->prior=s；s->next=p；p->prior>next=s；s->prior=p->prior； B. p->prior=s；p->prior->next=s；s->next=p；s->prior=p->prior； C .s->next=p；s->prior=p->prior；p->prior=s；p->right->next=s； D. s->next=p；s->prior=p->prior；p->prior>next=s；p->prior=s；
29、 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。
A.单链表 B.静态链表 C.线性链表 D.顺序存储结构 30、 栈和队列的共同点是 C 。
A.都是先进后出 B.都是先进先出
C.只允许在端点处插入和删除元素 D.没有共同点 31、 向一个栈顶指针为 hs 的链栈中插入一个 s 所指结点时，则执行 C 。
A. hs->next=s; B. s->next=hs->next; hs->next=s; C. s->next=hs; hs=s; D. s->next=hs; hs=hs->next;
32、 判定一个环形队列 qu（最多元素为 MaxSize ）为空的条件是 C 。 A. qu->rear-qu->front= =MaxSize B. qu->rear-qu->front-l==MaxSize C. qu->front= =qu->rear D. qu->front= =qu->rear+l 33、 若用一个大小为 6 的一维数组来实现环形队列，且当前 rear 和 front 的值分 别为
0 和 3。当从队列中删除一个元素，再加入两个元素后，rear 和 front 的 值分别是 B 。 A. 1 和 5 B. 2 和 4 C. 4 和 2 D. 5 和 1
34、 在一个链队中，假设 f 和 r 分别为队头和队尾指针，则删除一个结点的运算是 C。 A. r=f->next; B. r=r->next;
C. f=f->next; D. f=r>next; 35、 下图所示二叉树的中序遍历序列是 B 。
A. abcdgef B. dfebagc C. dbaefcg D. defbagc
36、 深度为 5 的二叉树至多有 C 个结点。
A. 16 B. 32 C. 31 D.10
37、 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则 D 。
A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 38、 下列说法正确的是 A 。
A、链栈没有容量限制 B、顺序栈没有容量限制 C、链队有容量限制 D、单向链表有容量限制 39、 在一个无向图中，所有顶点的度数之和等于所有边数的 C 倍。
A. 1/2 B. 1 C. 2 D. 4
40、 对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是
D 。
A. n B. (n-1)2 C. n-1 D. n2
41、 已知一个图如下图所示，若从顶点 a 出发按深度搜索法进行遍历，则可能得到
的一种顶点序列为 D ；按广度搜索法进行遍历，则可能得到的一 种顶点序列为 B 。
① A. a，b，e，c, d，f B. a，c，f，e，b，d
C. a，e，b，c，f，d D. a，e，d，f，c，b ② A. a，b，c，e，d，f B. a，b，c，e，f，d
C. a，e，b，c，f，d D. a，c，f, d，e，b
42、 顺序查找法适合于存储结构为 B 的线性表。
A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 43、 采用折半查找法查找长度为 n 的线性表时，每个元素的平均查找长度为 D 。
A.O(n2) B.O(nlog2 n) C.O(n) D. O(log2n)
44、 对有 18 个元素的有序表作折半查找，则查找 A[3] 的比较序列的下标为 D 。