内容发布更新时间 : 2024/5/20 17:00:10星期一 下面是文章的全部内容请认真阅读。
数据结构考试题（样例一）
一．选则题（5分）
1．数据结构中，与所使用的计算机无关的是数据的（3） 结构。 （1）存储（2）物理（3）逻辑（4）物理和存储 2．（4）在链表中进行比在顺序表中进行效率高。 （1）顺序查找（2）折半查找（3）分块查找（4）插入 3．树结构最适合于用来表示（3） 。
（1）有序数据（2）无序数据（3）元素间具有分支层次关系的数据 （4）元素间无关联的数据
4．散列存储中，碰撞（或称冲突）指的是（2） 。
（1）两个元素具有相同序号（2）不同的关键字对应于相同的存储地址 （3）两个记录的关键字相同（4）数据元素过多 5．n个结点的连通图至少有（1） 条边。 （1）n-1 （2）n （3）n(n-1)/2 （4）2n
6．直接选择排序的时间复杂性为（4） （n为元素的个数）。 （1）O(n) （2）O(log2 n) （3） O(n log2 n) （4） O(n2)
二．判断下列各命题是否正确，若正确在（ ）内打√，否则打×。（5分） 1．使用双向链表存储数据，可以提高查找（定位运算）的速度。（√） 2．B+ 树是一种特殊的二叉树。（×） 3．栈可视为一种特殊的线性表。（√） 4．最小生成树是边数最少的生成树。（√） 5．快速排序总是比其它排序方法快。（×） 三．填空（10分）
1．设二维数组A[10 . . 20, 5 . . 10] 按行优先存储，每个元素占4个单元，A[10, 5]的地址是2000，则A[15,10]的地址是 2140 。 2．深度为k的满二叉树有 2k - 1 个结点。
3．设s =?I AM A STUDENT?， t =?GOOD WORKER?， CONCAT(Substr(s，6，2)，t) =?A GOOD WORKER?。
4. ISAM文件由主索引，柱面索引，磁道索引和主文件组成。 5．散列既是一种存储 方式，又是一种查找方法。
四．应用题（40分）
1．（15分）已知某系统在通信联络中只可能出现8种字符。其频率分别为0.05, 0.29, 0.07, 0.08, 0.14, 0.23, 0.03, 0.11。试设计哈夫曼编码。 答案：
238291114735 19421005829150000000111111
哈夫曼编码: 0.05: 11111, 0.29: 10, 0.07: 1110, 0.08: 000, 0.14: 110, 0.23: 01, 0.03: 11110, 0.11: 001; 2．（15分）试编写算法实现下述运算：①图的广度优先搜索; ②图的连通分量计算。 答案：
const vnum = …； //图的顶点数 struct graph { int vex[vnum];
int arcs[vnum][vnum]; }; graph ga;
void dfs (vexnode *g[], int v1) //从V1出发深度优先遍历用链接表表示的图g { edgenode *p;
bool visited[n]; //访问标记数组，n为顶点数 cout< visited[v1] = true; //标志V1访问 p = g[v1]→link; //找V1的第一个邻接点 while (p != NULL) { if (!(visited [p→vertex]) dfs(g, p→vertex); p = p→next; //回溯 - 找V1邻接点 } } 在广度优先搜索中，若对x的访问先于y，则对x邻接点的访问也先于对y邻接点的访问。因此，可采用队列来暂存那些刚访问过，但可能还有未访问的邻接点的顶点。 void bfs (vexnode *g[], int v1) { //以邻接表为存储结构的广度优先搜索。q为队列，假设visited的各分量已置为false} int v; init_linkedque (q); //设置一个空队q visited[v1] = true; cout< in_linkedque (q, v1); //v1入队 while (!(empty (q)) { v = out_linkedeque (q); //出链队列 p = g[v]→link; while (p != NULL) { if (!visited[p→vertex]) { visited [p→vertex] = true; cout< in _linkedque (q, p→vertex); } p = p→next; } } } 如果要遍历一个非连通图，则需多次调用dfs或bfs。每一次都得到一个连通分量；调用dfs或bfs的次数就是连通分量的个数。 3．（10分）给出下图的所有拓扑排序序列。 1 答案： 2 3 ④→⑤→②→①→③； ⑤→④→②→①→③； ⑤→②→④→①→③。 4 5 五．设计题（40分） 1．（10分）写一个算法，借助栈将一个单链表倒置（可以用栈的基本运算）。也即，将下面的单链表： Head