7.广义表a=（a,b,(a,b,(a,b,……的长度为（ ）
a.1 b.2
c.3 d.无限值。
8.已知10×12的二维数组a，按“行优先顺序”存储，每个元素占1个存储单元，已知a[1][1]的存储地址为420，则a[5][5]的存储地址为（ ）
a.470 b.471
c.472 d.473
9.在一棵二叉树中，度为2的结点数为15，度为1的结点数为3，则叶子结点数为（ ）
a.12 b.16
c.18 d.20
10.在带权图的最短路径问题中，路径长度是指（ ）
a.路径上的顶点数 b.路径上的边数。
c.路径上的顶点数与边数之和 d.路径上各边的权值之和。
11.具有n个顶点、e条边的无向图的邻接矩阵中，零元素的个数为（ ）
b.2e 12.要以o（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ ）
a.归并排序 b.快速排序。
c.堆排序 d.冒泡排序。
13.若希望在1000个无序元素中尽快求得前10个最大元素，应借用（ ）
a.堆排序 b.快速排序。
c.冒泡排序 d.归并排序。
14.对有序表进行二分查找成功时，元素比较的次数（ ）
a.仅与表中元素的值有关 b.仅与表的长度和被查元素的位置有关。
c.仅与被查元素的值有关 d.仅与表中元素按升序或降序排列有关。
15.散列文件是一种（ ）
a.顺序存取的文件 b.随机存取的文件。
c.索引存取的文件 d.索引顺序存取的文件。
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16.若一个算法中的语句频度之和为t（n）=3n3-200nlog2n+50n，则该算法的渐近时间复杂度为。
17.在单链表中，除了第1个元素结点外，任一结点的存储位置均由指示。
18.栈的修改是按的原则进行。
19.字符串中任意个连续的字符组成的子序列称为该串的。
20.假设一个10阶的上三角矩阵a按行优先顺序压缩存储在一维数组b中，若矩阵中的第一个元素a11在b中的存储位置k=0，则元素a55在b中的存储位置k
21.在一棵具有n个结点的严格二叉树中，度为1的结点个数为。
22.对于稀疏图，采用表示法较为节省存储空间。
23.在排序过程中，如果则称其为外部排序。
24.设有一组记录的关键字为｛19，14，23，1，68，12，10，78，25｝，用链地址法构造散列表，散列函数为h（key）=key％11,散列地址为1的链中有个记录。
25.多关键字文件的特点是除主文件和主索引外，还建有。
三、解答题（本大题共4小题，每小题5分，共20分）
26.对于下列稀疏矩阵（注：矩阵元素的行列下标均从1开始）
1）画出三元组表；
2）画出三元组表的行表。
27.已知一个森林的前序遍历序列为cbadhegf，后序遍历序列为abcdefgh。
1）画出该森林；
2）画出该森林所对应的二叉树。
28.对关键字序列（429，653，275，897，170，908，473，256，726）进行基数排序，写出每一趟的排序结果。
29.对下列关键字序列。
构造散列表，假设散列函数为h（key）=key％13,用拉链法解决冲突。
1）画出该散列表；
2）求等概率情况下查找成功的平均查找长度asl;
3）写出删除值为70的关键字时所需进行的关键字比较次数。
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.阅读下列算法，并回答问题：
1）假设l=（3，7，7，11，20，20，20，51，51），写出执行函数f30（&l）后的l；
2）简述f30的功能。
void f30(seqlist*l)
五、算法设计题（本题10分）
34.设顺序表ｌ是一个递增有序表。编写算法，要求利用二分查找法确定插入位置，将元素ｘ插入到ｌ中，使ｌ保持有序。