A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序
2． 已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A. head->priro==NULL B. head->next==NULL
C. head->next==head D. head->next-> priro==NULL
4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为：
A) 2 B) 3 C) 4 D) 5 5. 以下哪一个不是队列的基本运算？
A）从队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值 6. 在长度为n的顺序表的第i个位置上插入一个元素（1≤ i ≤n+1），元素的移动次数为： A) n – i + 1 B) n – i C) i D) i – 1 7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为: A) 顺序表 B) 用头指针表示的循环单链表 C) 用尾指针表示的循环单链表 D) 单链表
8．对包含n个元素的哈希表进行查找，平均查找长度为：
A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n
9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点
进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A、48 B、49 C、50 D、51
10．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：
A）3 B）2 C）4 D）5 四、填空题（10分，每空1分）
1．填空完成下面一趟快速排序算法：
int QKPass ( RecordType r [ ], int low， int high) { x = r [ low ]；
while ( low < high ) {
while ( low < high && r [ ]. key >= x.key )
high - -； if ( low < high )
{ r [ ] = r [ high ]； low++; }
while ( low < high && r [ ]. key < x. key ) low++;
if ( low < high )
{ r [ ] = r [ low ]； high--; } }
r [ low ] = x； return low ;
}
2. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句： ； ；R=S；
3．通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣。 4．已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序
存储，则排在第8个位置的元素是： 5．高度为h的完全二叉树最少有 个结点。
五、构造题（20 分） 1．（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。
DS = (D, R)
D = { a, b, c, d, e, f, g } R = { T }
T = { , ,
2．（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为H(K) =（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下查找成功的平均查找长度。
3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53， 87）调整为大根堆。 4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。
六、算法分析题（10分）
阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。 （1） 简要说明程序功能。（5分） （2） n个结点的满二叉树的深度h是多少？（3分） （3） 假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）
int Proc (BSTree *bst, KeyType K) { BSTree f, q, s;
s=(BSTree)malloc(sizeof(BSTNode));
s-> key = K; s-> lchild = NULL; s-> rchild = NULL; if ( *bst == NULL ) { *bst = s; return 1; } f = NULL; q = *bst; while( q != NULL )
{ if ( K < q -> key )
{ f = q; q = q -> lchild; } else
{ f = q; q = q -> rchild; }
}
if ( K < f -> key ) f -> lchild = s; else f -> rchild = s; return 1; }
七、算法设计题（25分）
1． 已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）
2． 无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分）
3． 编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）
数据结构 附录A 样卷一参考答案 一：判断题
题号 答案 1 × 2 × 3 √ 4 × 5 √ 6 √ 7 √ 8 √ 9 × 10 × 二：选择题
题 1 2 C 3 A 4 D 5 D 6 D 7 B 8 D 9 D 10 11 A A 12 13 14 15 16 17 18 19 20 C B C C B C B C B 答 B 三：填空
1表长的一半 2 排好序列 3， 4 312 5 N+1 6 S->next=P->next P->next=S 7 路径递增 8 Log(2)(N) 9中序 10 97 11 链域个数不同 12 63 13 1476 14 P->next=head 15 散列查找 16 先进先出 17 5 18 FDBECA 19将矩阵第i行全部置0
四，构造题 1，
计算函数值
key Key%7 75 5 33 5 52 3 41 6 12 5 88 4 66 3 27 6 (1)哈希表（4分，每对1个0.5分）
index key 0 27 1 2 3 52 4 88 5 75 6 33 7 41 8 12 9 66 (2)比较次数（3分）
key Cmp 75 1 33 2 52 1 41 2 12 4 88 1 66 7 27 5 ASL=(1+2+1+2+4+1+7+5)/8=23/8
5， (1)
3 1 5 6 7 (2) ASL=(1+2*2+4*3+1*4)/8=21/8=2.62
0 2 4
《数据结构》附录B 样卷二 参考答案
一、简答题（15分，每小题3分） 6. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。 7. 主要与哈希函数、装填因子α有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。 8. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。 9. 头指针指向头结点，头结点的后继域指向首元素结点。 10. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。 二、判断题（10分，每小题1分）
（1）(√) （2）(×) （3）(×) （4）(√) （5）(×) （6）(√) （7）(×) （8）(√) （9）(×) （10）(×) 三、单项选择题（10分, 每小题1分） 1． D） 2． B） 3． C） 4. C） 5. B） 6. A) 7． C) 8． D) 9． C） 10．C） 四、填空题（10分，每空1分） 1． high low low high 2. S->next=R->next ； R->next=S ； 3． 时间 空间 4． A[2, 3] 5． 2 五、构造题（20 分） 1．（4分） h-10 1 2 THU 3 FRI 4 WED 5 TUE 6 SAT 7 8 9 SUN MON 2．（6分） ASLsucc = ( 1×4 + 2×2 + 3 ) / 7 = 11 / 7 3.（6分） 4．（4分）已知权值集合为：{ 5，7，2，3，6，9 }，要求给出哈夫曼树，并计算其带权路径长度WPL。 WPL = 2×( 9 + 6 + 7 ) + 3×5 + 4×( 2 + 3 ) = 79 六、算法分析题（10分） 解： （1） 在二叉排序树中插入关键字为K的结点