浙江理工大学 2012 年数据结构

贡献者： xzllxls

1. 一、单选题(每题 2 分 ,共 20 分)

　　 1.不带头结点的单链表 simpleList 为空的判定条件是
A. simpleList==null
B. simpleList->next==null
C. simpleList->next=simpleList
D. simpleList!=null

　　 2.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一一个结点 ,故采用（）存储方式最节省运算时间。
A.单链表
B.仅有头结点的单循环链表
C.双链表
D.仅有尾指针的单循环链表

　　 3.向一个栈顶指针为 top 的链栈中插入一个 $S$ 所指结点时,则执行（ ）。
A. top->next=S;
B. S->next= top-> next;top-> next=S;
C. S->next=top;top=S;
D. S-> next=top;top=top->next;

　　 4. 一维数组和线性表的区别是
A.前者长度固定,后者长度可变
B.后者长度固定，前者长度可变
C.两者长度均固定
D.两者长度均可变

　　 5. 设矩阵 A 是-一个对称矩阵, 为了节省存储,将其下三角部分按行序存放在一维数组 B[1,n(n-1)/2]中 , 对任一下三角部分中任-元素 a:(i≥j),在一-组数组 B 的下标位置 K 的值是
A. i(i-1)/2+j-1
B. i(i-1)/2+j
C. i(i+1)/2+j-1
D. i(i+1)/2+j

　　 6. 在线索化二叉树中, $P$ 所指的结点没有左子树的充要条件是
A. P->left==null
B. P->ltag=1
C. P->Itag==1 且 P->left==null
D. 以上都不对

　　 7. 如果 Tree2 是由有序树 Tree1 转换而来的二 叉树,那么 Tree1 中结点的后序就是 Tree2 中结点的（）。
A.先序 $$ B.中序 $$ C.后序 $$ D.层次序

　　 8. 判定一个有向图上是否存在回路除了可以利用拓扑排序方法外,还可以用（ ）
A.求关键路径的方法
B.求最短路径的 Dijkstra 方法
C.广度优先遍历算法
D.深度优先遍历算法

　　 9. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的.
A.先序遍历
B.中序遍历
C.后序遍历
D.按层遍历

　　 10. 采用折半查找法查找长度为 $n$ 的线性表时，每个元素的平均查找长度为（ ）
A. $O(n^2)$
B. $O(nlo{g}_{2}n)$
C. $O(n)$
D. $O(lo{g}_{2}n)$

2. 二、填空题(每空 2 分 ,共 30 分)

　　 1. 在循环双链表的 P 所指结点之前插入 S 所指结点的操作如下:

S->next=P;
S->prior=（    ）;
P->prior-> next=S;
P->prior=S;

　　 2. 分析以下程序段的时间复杂度为（ ）

k=1;
while(k<=n)
    k=k*2;

　　 3. 向一个长度为 $n$ 的顺序表中的第 $i$ 个元素($0$⩽$i$⩽$n-1$)之前插入一个元素时,需向后移动（ ）个元素。

　　 4. 设有一个背包可以放入的物品重为 S , 现有 n 件物品,重分别为 W1 , W2, . .。, Wn。问能否从这 n 件物品中选择若干件放入背包,使得放入的重量之和正好是 S。设布尔函数 Knap(S , n)表示背包问题的解, W:(i=1, 2，. . .，n)均为正整数,并已顺序存储地在数组 W 中。请在下列算法的下划线处填空,使其正确求解背包问题。

Knap(S , n)
若S=0
则Knap←-true;
否则若( S<0 )或(S>0且n<1)
则Knap←false;
否则若Knap__ (1)__ =true
则print(W[n]) ; Knap←true;
否则Knap←Knap_ (2)_ ;

　　 5.下列程序判断字符串 s 是否对称 ,对称则返回 1 ,否则返回 0 ;如 f("abba")返回 1 ,f("abab' )返回 0 ;

intf( (1)_ )
inti=0j=0;
while(s[j])_ (2)_ ;
fi--j&j&si[=ij;++j-);
return( (3)_)

　　 6.一个有 $n$ 个顶点的无向图最多有（）边。

　　 7.在堆排序和快速排序中,若原始记录接近正序或反序,则选用（）比较好。

　　 8.二叉树的先序遍历和中序遍历如下:先序遍历: EFHIGJK ;中序遍历: HFIEJKG。该二叉树根的右子树的根是（）。

　　 9.已知有向图 G=(V,E) ,其中 V={V1,V2,V3,V4,Vs,Vs,Vz}，E={<V1,V2>,<V1,V3>,<V1V4>.<V2,Vs>.<V3,Vs>. <V3,V6>.<V4,V6>,<Vs,.V>, <V6,V>>},G 的一种拓扑序列是（）。

　　 10.采用邻接表存储的图的广度优先遍历算法类似于二叉树的（）.

　　 11.设有一-组记录的关键字为{19, 14, 23, 1, 68, 20, 84, 27 , 55, 11, 10 , 79} ,用链地址法构造散列表,散列函数为 H(key)=key MOD 13 ,散列地址为 1 的链中有（）个记录。

　　 12.对数列{25 , 84, 21, 47, 15, 27 , 68, 35 , 20}进行排序,元素序列的变化情况如下: (1)25,84,21,47,15,27,68,35,20(2)20,15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47，68,84(4)15,20,21,25,27,35,47,68,84,则采用的排序方法是（）

3. 三、判断题(每题 2 分,共 20 分)

　　 1.数据的逻辑结构是指数据元素之间的逻辑关系。()

　　 2.一个数据结构在计算机中的映像称为存储结构。()

　　 3.数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。( )

　　 4.引入二叉线索树的目的是加快查找结点的前驱或后继的速度。( )

　　 5.直接定址法得到的哈希函数肯定不会发生冲突。( )

　　 6.在分块查找中,首先查找块表,然后再查找相应的索引表。( )

　　 7.查找效率最高的二又树是所有结点的右子树都为空的二叉树。( )

　　 8.具有 n 个顶点的无向连通图中至少有 n-2 条边。( )

　　 9.一个图的邻接表表示法是唯一的,而邻接矩阵表示法是不唯一的。( )

　　 10.如果含有 n 个顶点的图 G 形成一个环 ,则 G 有 n-1 棵生成树。( )