二叉树的先序遍历序列中的最后一个结点。(对 )
135． 希尔排序算法的时间复杂度为O(n2)。(错 )
136． 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无
关而与图中边数有关。(错 )
137． 中序遍历一棵二叉排序树可以得到一个有序的序列。(对 )
138． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情
况。(对 )
139． 顺序表查找指的是在顺序存储结构上进行查找。（错 ） 140． 堆是完全二叉树，完全二叉树不一定是堆。（对 ） 141． 调用一次深度优先遍历可以访问到图中的所有顶点。（错）
142． 分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
（对 ）
143． 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ 对） 144． 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（对） 145． 设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
（错）
146． 层次遍历初始堆可以得到一个有序的序列。（错 ）
147． 设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（对） 148． 线性表的顺序存储结构比链式存储结构更好。（错） 149． 中序遍历二叉排序树可以得到一个有序的序列。（对 ） 150． 快速排序是排序算法中平均性能最好的一种排序。（对 ）
151． 不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”
情况。（对）
152． 当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（对） 153． 设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为
第 36 页 共 100 页
O(log2n)。（ 对）
154． 完全二叉树中的叶子结点只可能在最后两层中出现。（对） 155． 哈夫曼树中没有度数为1的结点。（对 ）
156． 对连通图进行深度优先遍历可以访问到该图中的所有顶点。（对 ） 157． 先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（对 ） 158． 由树转化成二叉树，该二叉树的右子树不一定为空。（错 ） 159． 线性表中的所有元素都有一个前驱元素和后继元素。（错 ） 160． 带权无向图的最小生成树是唯一的。（错 ）
161． 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。
（对 ）
162． 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。
（错 ）
163． 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字
可能存在的块号，然后再在相应的块内进行顺序查找。（对 ）
164． 二维数组和多维数组均不是特殊的线性结构。（错 ）
165． 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。
（错 ）
166． 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。
（对 ）
167． 非空的双向循环链表中任何结点的前驱指针均不为空。（对 ）
168． 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时
间复杂度均为O(n)。（对 ）
169． 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶
点是否被访问过。（对 ）
170． 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。
第 37 页 共 100 页
（对 ）
171． 数据元素是数据的最小单位。 （对）
172． 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执
行时间最省。 （ ）
173． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、
删除等操作。 （ ）
174． 在树中，如果从结点K出发，存在两条分别到达K'，K\的长度相等的路径，
则结点K'和k\互为兄弟。 （ ）
175． 最佳两叉排序树的任何子树都是最佳的。 （ ）
176． 算法和程序没有区别，所以在数据结构中两者是通用的。 （ ） 177． 顺序存储方式只能用于存储线性结构。 （ ）
178． 在线性表链式存储结构中， 逻辑上相邻的元素在物理位置上不一定相邻。
（ ）
179． 如果某种排序算法是不稳定的，则该算法没有实际意义。 （ ） 180． 当两个字符出现的频率相同时，则其哈夫曼编码也相同。 （ ）
三、程序选择填空
1.下列程序的算法是统计一个链队列HQ的结点个数。试在下列(A)~(H)选项中选择
正确语句填入各空白处。
int count(structure LinkQueue *HQ) {
struct LinkQueue *p; n=0;
(1) B ; while ( (2) G ) { n++; p=p->next; }
第 38 页 共 100 页
return(n); }
(A)p=HQ->front (B)p=HQ->front->next (C)p=HQ->rear (D)p=HQ->rear->next (E)p!=NULL (F)p!=HQ->front (G)p!=HQ->rear (H)p->next!=HQ->front
2.下列程序的算法是在一个带头结点的单链表为尾端增加一个新结点，并将单链表
改造成循环链表。试在下列(A)~(H)选项中选择正确语句填入各空白处。 void add(struct node *head, int x) {
struct sequence *p,*q,*head;,*s;
s=(struct node *)malloc(sizeof(struct node)); s->data=x; p=head->next; q=head;
(3) F; while (p!=NULL) { q=p; p=p->next; }
(4) A ; }
(A)q->next=s (B)p->next=s (C)p=s
(D)q=s (E)p->next=head (F)s->next=head (G)p=head (H)q=head
3.下列程序的算法是将一个已知的单向链表改造成双向链表，即根据单向链表中的
*next指针域，设置*prior指针域的值。试在下列(A)~(H)选项中选择正确语句填入各空白处。
void add(struct node *head) {
struct node *p,*q; p=head; q=head->next; while(q!=NULL) { (5) G ; p=q;
(6) A ;
第 39 页 共 100 页
} }
(A)q=q->next (B)p=p->next (C)p=q->next (D)q->next=p (E)p->prior=q (F)p=q->prior (G)q->prior=p (H)q=p->prior
4.下列程序的算法是在一个已经中根线索化的二叉树上检索某结点的前趋结点。试
在下列(A)~(H)选项中选择正确语句填入各空白处。 struct nodex *inpre(struct nodex *p) {
if (p->ltag==1) q=p->lch; else {
(7) B ; while (r->rtag!=1) - (8) C ; q=r; } return(q); }
(A)r=p->rch (B)r=p->lch (C)r=r->rch (D)r=r->lch (E)r=q->rch (F)r=q->lch (G)q=p->rch (H)q=p->lch
5.下列程序是从一维数组A[n]中折半查找关键字为K的元素的递归算法，若查找成
功则返回对应元素的下标，否则返回-1。试在下列(A)~(H)选项中选择正确语句填入各空白处。
int Binsch(ElemType A[], int low, int high, KeyType K ) {
int low,high; if (low<=high) {
int mid=(low+high)/2; if (K==A[mid].key) return mid; else if (K
else return -1;
第 40 页 共 100 页