图2 题6图
02年北京文考“数据结构”试题
一、判断题 (每小题1分，共15分)
1.程序就是算法，但算法不一定是程序。( )
2.线性表只能采用顺序存储结构或者链式存储结构。( )
3.线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。( ) 4.除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。( ) 5.稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。( ) 6.不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。( ) 7.确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。( ) 8.深度为h的非空二叉树的第i层最多有2i-1 个结点。( ) 9.满二叉树就是完全二叉树。( )
10.已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。( ) 11.非空二叉排序树的任意一棵子树也是二叉排序树。( )
12.对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。( ) 13.若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。( )
14.散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。( ) 15.序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。( ) 二、单项选择题 (每小题2分，共20分) 1.算法分析的目的是( )
A.研究算法的输入与输出之间的关系 B.找出数据结构的合理性 C.分析算法的效率以求改进算法 D.分析算法的可读性与可移植性
2. 在由list所指的非空线性链表中删除由p指的链结点的下一个链结点的过程是依次执行q←link(p),____________,call RET(q)。( ) A.link(p)←q B.link(q)←p
C.link(q)←link(p) D.link(p)←link(q)
3.依次在初始为空的队列中插入元素为a,b,c,d以后，紧接着作了两次删除操作，此时的队头元素是( ) A.a B.b C.c D.d
4.若某堆栈的输入序列为 1，2，3，?，n-1，n，输出序列的第1个元素为n，则第个输出元素为( ) A.n-i+1 B.n-1
C.i D.哪个元素无所谓
5.设计递归问题的非递归算法一般需要用到__________机制。( ) A.数组 B.堆栈 C.队列 D.二叉树
6.已知非空二叉树采用顺序存储结构，树中结点的数据信息依次存放在一个一维数组中，即 ABC□DEF□□G□□H□□ 该二叉树的中序列遍历序列为( ) A.G,D,B,A,F,H.C,E B.G,B,D,A,F,H,C,E C.B,D,G,A,F,H,C,E D.B,G,D,A,F,H,C,E
7.在一棵度为3的树中，度为3的结点有2个，度为2的结点有1个，度为1的结点有2个，那么，该树有__________个叶结点。( ) A.4 B.5 C.6 D.7
8.已知有向图G=，其中V＝{v1,v2,v3,v4,v5,v6},E＝{,，，，，，，}，G的拓扑序列是______。( )
A.v3,v1,v4,v5,v2,v6 B.v3,v4,v1,v5,v2,v6 C.v1,v3,v4,v5,v2,v6 D.v1,v4,v3,v5,v2,v6
9.在初始为空的散列表中依次插入关键字序列(MON,TUE,WED,THU,FRI,SAT,SUN),散列函数为H(k)=i MOD 7，其中，i为关键字k的第一个字母在英文字母表中的序号，地址值域为 [0:6] ，采用线性再散列法处理冲突。插入后的散列表应该如__________ 所示。( ) A. 0 1 2 3 4 5 6
THU TUE WED FRI SUN SAT MON B. 0 1 2 3 4 5 6
TUE THU WED FRI SUN SAT MON C. 0 1 2 3 4 5 6
TUE THU WED FRI SAT SUN MON D. 0 1 2 3 4 5 6
TUE THU WED SUN SAT FRI MON
10. 对数据元素序列(49，72，68，13，38，50，97，27)进行排序，前三趟排序结束时的结果依次为：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；该排序采用的方法是( )
A.插入排序法 B.选择排序法 C.泡排序法 D.堆积排序法
三、填空题 (每小题2分，共20分)
1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的数据元素前，需要先依次移动_________个数据元素。
2.在非空双向循环链表中由q所指的那个链结点后插入一个由p指的链结点的动作对应的语句依次为：llink(p)←q，rlink(p)←rlink(q)，rlink(q)←p,______________。(空白处为一条赋值语句)
3.已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=________________。 4.具有2000个结点的二叉树，其深度至少为_________。
5.具有n0个叶结点的哈夫曼树 (Huffman) 的分支总数为_________。 6.若连通图的顶点个数为n，则该图的生成树的边数为_________。
7.在序列(2，5，8，11，15，16，22，24，27，35，40)中采用折半查找(二分查找)方法查找元素24，需要进行_________次元素之间的比较。
8.索引文件中的索引表是_________提供的，并且索引表的表项按_________有序列排列。
9.对具有n个元素的任意序列采用插入排序法进行排序，整个排序过程中要进行_________次元素之间的比较。
10.插入排序法、选择排序法、拓扑排序法与归并排序法中，_________不是内排序方法。
四、问题求解题 (每小题10分，共20分)
1.已知一带权连通图采用邻接矩阵存储方法，并且邻接矩阵采用三元组表表示，其中，第一个三元组 (5，5，16)分别表示邻接矩阵的行数、列数字与非零元素的个数，从第二个三元组开始，依次按行序为主序的次序分别给出16个非零元素，它们依次为(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；请分别画出该带权连通图的两棵最小生成树。
2.已知散列范围为[0：9]，散列函数为H(key)=key MOD 9，处理冲突的方法为链地址法，请画出依次插入关键字8,10,14,19,21,23,28,32以后的哈希表。 五、算法题 (本题共25分)
1. (10分)下面的算法将一维数组A[1:n]中所有奇数移到数组的左边，所有偶数字移到数组的右边。请在算法的空白处填入适当内容，使之能够正常工作。(提示：用 x MOD y表示求x除以y的余数) procedure EXCHANGE(A,n) i←1 j←n repeat
while_________do // 当A[i]为奇数时 // i←i+1 end
while_________do // 当A[i]为偶数时 // j←j-1 end
if(i [ temp←A[i]
A{i}←A[j]
______________ ] // 交换A[i]与A[j]的位置 // else exit
until __________ end
2.(15分) 已知非空线性链表的链结点的构造为 date | link，第一个链结点的指针为list，下面的算法在链表的第i个链结点(设i>0)前插入一个数据信息为item的新结点。请在算法的空白处填入适当内容，使之能够正常工作。 procedure INSERT (list,i,item) if (i=1) then
[ call GETNODE (p) // 申请一个新的链结点 // date (p) ←item link (p) ←list
________________ // 将新结点插在第1个链结点前 // else [ q←list
for j←1 to___________do r←q
q←link (q)
if__________then
[call ERROR (\超过链表的长度!\return ]
end // r与q分别指向第i-1个与第i个链结点 // call GETNODE (p) // 申请一个新的链结点空间 // data (p) ←item link (p) ←q
__________________] // 将新结点插在第i个结点前 // end