装 ： 号学订： 名姓线 ： 级班
江苏技术师范学院东方学院2007—2008学年第2学期
《数据结构与算法》试卷（1B）
注意事项：
1．本试卷适用于2006级计算机专业学生使用。 2．本试卷共6 页，满分100分，答题时间120分钟。 3．请用蓝或黑色墨水的钢笔、圆珠笔或签字笔书写。
题号 一 二 三 四 五 总分 得分 得分 评卷人 一、单项选择题（本大题共10道小题，每小题1.5分，共15分）
请将答案填于下面的表格，否则该题0分计
题号 1 2 3 4 5 6 7 8 9 10 答案
1、在长度为n的顺序表的任意位置插入一个新元素的渐进时间复杂度为( )。A. O(n) B. O(n/2) C. O(1) D. O(n2)
2、当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( )。
A. n-2 B. n-1 C. n D. n+1 3、链表表示线性表的优点是( )。
A. 便于随机存取 B. 花费的存储空间比顺序表少 C. 便于插入与删除 D. 数据元素的物理顺序与逻辑顺序相同 4、设有两个串p和q，求q在p中首次出现的位置的运算称作( )。
A. 连接 B. 模式匹配 C. 求子串 D. 求串长
5、设有一个二元数组A[m][n],假设A[0][0]存放位置在4(10) ,A[2][2]存放位置在676 (10)，每个元素占一个空间，则A[4][5]在（ ）位置,(10)表示用
10进数表示。
A. 692(10) B. 626(10) C. 709(10) D. 724(10)
《数据结构与算法》试卷(1B) 第 1 页 共 6 页
6、在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( )。
A. 2 B. -1 C. 0 D. 1 7、n个顶点的连通图至少有( )条边。
A. n+1 B. n C. n-1 D. 0 8、无向图中一个顶点的度是指图中( )。
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数 C. 通过该顶点的回路数 D. 与该顶点连通的顶点数
9、在下列排序算法中，( )算法的最坏情况下时间复杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10、下列说法中错误的是( )。
A. n个结点的树的各结点度数之和为n-1 B. n个结点的无向图最多有n*(n-1)条边
C.用相邻矩阵存储图时所需存储空间大小与图的结点数有关,而与边数无关 D.散列表中碰撞的可能性大小与负载因子有关
得分 评卷人 二、填空题（本大题共15空，每空1分，共15分） 1、数据结构有如下四类基本结构：集合、_________________、_________________、_________________。
2、在顺序表中插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与________________有关。
3. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 ________。不允许插入和删除运算的一端称为________。
4、____________________________________称为空串；
5、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址，则数组A的体积（存储量）为_______________。
6、一棵具有257个结点的完全二叉树，它的深度为________。
7. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的_______。 8、图的深度优先遍历序列______惟一的。 9、从平均时间性能而言，__________排序最佳。
《数据结构与算法》试卷(1B) 第 2 页 共 6 页
10、线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用折半法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索______次。设有100个结点，用折半查找时，最多比较次数是______。
得分 评卷人 三、判断题（本大题共10小题，每小题1分，共10分） 正确的打“√”，错误的打“×”
( )1. 记录是数据处理的最小单位。
( )2. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。
( )3. 栈和队列是一种非线性数据结构。
( )4．若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。 ( )5. 从逻辑结构上看，n维数组的每个元素均属于n个向量。 ( )6. 稀疏矩阵压缩存储后，必会失去随机存取功能。 ( )7.二叉树中每个结点的两棵子树的高度差等于1。 ( )8．强连通图的各顶点间均可达。
( )9．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。
( )10．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。 得分 评卷人 四、简答、应用题（共40分）
1、数据结构的主要研究对象是什么？(4分)
2．线性表有两种存储结构：一是顺序表，二是链表。试问：
《数据结构与算法》试卷(1B) 第 3 页 共 6 页
（1）如果有 n个线性表同时并存,并且在处理过程中各表的长度会动态变化,线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？(4分)
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ (4分)
3. 设循环队列的容量为40(序号从0到39)，现经过一系列的入队和出队运算后，有：① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？（6分）
4. 已知二维数组Am×m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。（4分）
5. 一棵度为2的树与一棵二叉树有何区别？(4分)
6. 已知图1所示的有向图，请给出该图的:(8分)
《数据结构与算法》试卷(1B) 第 4 页 共 6 页
(1) 每个顶点的入/出度； (2) 邻接矩阵； (3) 邻接表； (4) 逆邻接表。 顶点 入度 出度
7．设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。（6分）
1 2 3 4 5 6 得分 评卷人 五、算法设计题（共20分）
1. 写出求二叉树深度的算法。（10分）
《数据结构与算法》试卷(1B) 第 5 页 共 6 页
2．已知11个元素的有序表为（05,13,19,21,37,56,,75,80,88,92）, 请写出折半查找的算法程序，查找关键字为key的数据元素。（10分）
《数据结构与算法》试卷(1B) 第 6 页 共 6 页