3）345，829，765，542，412，395，341，363
4）965，741，259，478，375，349，360，363
A）仅1）2） B）仅1） 2）3）
a
C）仅1）4） D）仅2）
13
13、对序列 { 15, 9, 7, 8, 20, -1, 4 } 用希尔排序
方法排序，经一趟后序列变为{ 15, -1, 4, 8, 20,
B．S[top]=x; top += 1;
c
C．top -= 1; S[top]=x;
D．S[top]=x; top --;
5
5、下列说法正确的是（ ）
b
(1) 稀疏矩阵压缩存储后，必会失去随机存取功能。
(2) 若一个广义表的表头为空表，则此广义表亦为空表。
(3) 广义表的取表尾运算，其结果通常是个表，但有时 也可是个单元素值。
9, 7 }，则该次采用的增量是（ ）
d
A．1 B．2
C．3
D．4
14
14、下列说法中，错误的是（ ） a (1) 外部排序是把外存文件调入内存，可利用内
部排序的方法进行排序，因此排序所花的时间 取决于内部排序的时间 (2) 在外部排序时，利用败者树方法选择当前最 小关键字过程的复杂度取决于归并的路数。 (3) 影响外排序的时间因素主要是内存与外设交 换信息的总次数。 A．仅(1) B．仅(1)(2) C．仅(2)(3) D．(1)(2)(3)
(4) 从逻辑结构上看，n维数组是由多个n-1维的数组构 成。
A．仅(1)(2)
B．仅(1)(4)
C．仅(2)(3)
D．仅(3)(4)
6
6、下列说法错误的是（ ）
c
① 在图G的最小生成树G1中，可能会有某条边 的权值超过未选边的权值。
Hale Waihona Puke ② 不同求最小生成树的方法得到的生成树是相 同的.
③ 当改变网上某一关键路径上任一关键活动后， 必将产生不同的关键路径
15
15、有n个叶子的哈夫曼树的结点总数为 d （ ）。
A．不确定 D．2n-1
B．2n
C．2n+1
16
填空题
1、用S表示入栈操作，X表示出栈操作，若元 素入栈的顺序为1234，为了得到1342出栈顺序， 相应的S和X的操作串为（ ）。
2、若用一个大小为6的数组来实现循环队列， 且当前rear和front的值分别为0和3，当从队列 中删除一个元素，再加入两个元素后，rear和 front的值分别为（ ）。
习题选讲
数据结构与算法分析
1
一．单项选择题
1、下面程序段的时间复杂度为（） b ◦ A. O (n) B. O (n^2) ◦ C. O (n(n-1)/2) D. O (logn)
void fun1(int n) {
x = 0; for ( i=0; i<n; i++ )
for ( j=i+1; j<n; j++ ) x++;
10
10、已知有向图G=(V,E)，其中V={ V1, V2, V3, V4, V5, V6, V7 }，E={ <V1,V2>, <V1,V3>,
<V1,V4>, <V2,V5>, <V3,V5>, <V3,V6>,
<V4,V6>, <V5,V7>, <V6,V7> }，G的拓扑序列
是（ ）
A．V1, V3, V4, V6, V2, V5, V7
C．表必须有序，而且只能从小到大排列
D．表必须有序，且表只能以顺序方式存储
12
12、设二叉排序树中关键字由1到1 000的整数组成， 现要查找关键字为363的结点，下述关键字序列中 不可能是在二叉排序树中查到的序列（ ）
1）51，250，501，382，320，340，390，363
2）24，877，125，342，421，623，501，363
a
B．V1, V3, V2, V6, V4, V5, V7
C．V1, V3, V4, V5, V2, V6, V7
D．V1, V2, V5, V3, V4, V6, V7
11
11、下面关于折半查找的叙述中，正确的是
（）
d
A．表必须有序，表可以顺序方式存储，也可
以链表方式存储
B．表必须有序且表中数据必须是整型，实型 或字符型
式为（ ）
d
◦ A．-A+B*C/DE
◦ B．-A+B*CD/E
◦ C．-+*ABC/DE
◦ D．-+A*BC/DE
9
9、设森林F中有三棵树，第1、第2和第3棵树 的结点个数分别为M1、M2和M3（M1，M2， M3皆大于0）。与森林F对应的二叉树根结点 的右子树上的结点个数是（ ）
d
◦ A．M1 ◦ B．M1+M2 ◦ C．M3 ◦ D．M2+M3
④ 网络的最小生成树是唯一的
◦ A12 B23 C234 D14
7
7、有n个叶子的哈夫曼树中分支节点总数为
（ ）。
a
A．n-1
B．2n+1
C．n+1
D．不确定
n+n2 = 2n2+1
n = n2+1
n2 = n-1
8
8、已知一算术表达式的中缀形式为：A+B*C-
D/E，后缀形式为：ABC*+DE/-，则其前缀形
}
2
2、若某线性表最常用的操作是删除最后一个 结点，则采用存储结构算法的时间效率最高的
是（）
◦ a. 单链表
d
◦ b. 给出表尾指针的单循环链表
◦ c. 双向链表
◦ d. 给出表尾指针双向循环链表
3
3、在单链表指针为p的结点之后插入指针为s的 结点，正确的操作是（ ）
A．p->next=s; s->next=p->next;
S×SS×S××
2和4
17
3、广义表A = ( a, b, ( (c, d), (e, (f, g)) ) )，则 Head( Tail( Head( Tail( Tail( A ) ) ) ) ) 的值为 （ ）。
4、在一棵高度为4的完全3叉树中，结点总数 在（ ）之间。
5、假设一个森林由4个节点构成，则森林可能 的形态有（ ）种（假设森林中的树不计顺序， 树中的各个子树也不计顺序）。
b
B．s->next=p->next; p->next=s;
C．p->next=s; p->next=s->next;
D．s->next=p; p->next=s;
4
4、若一个栈以向量 S[ 1..n ] 存储，初始栈顶指 针top为n+1，则下面x进栈的正确操作是（ ）
A．top += 1; S[top]=x;