数据结构与算法复习题

1、考生注意：1、学号、姓名、 年级、专业等应填 写准确“2、考试作弊 者，员令停考，成 绩作废。广西民族大学成人高等教育考试复习题课程名称：数据结构与算法考试fi期：20年 月考核时长:120分伸得分评卷人答案教学点考核方式：开卷试卷类别：b卷年级20级层次形式高起专命题教师张桂芬教研室主任一、单项选择题。(每题2分，共20分)1. 以下程序段中带硝句的执行频度和算法的时间复杂度分别是().for (i=l; i<= n ; +i )for (j=i+l; j<=n; +j) 0 mi;a. n(n-l)/2： n2 b. n2； n2c. n(n-l)/2： n d. n； n2.

2、 下列排序方法中是秘定排序的是(b >.a.希尔排序b.归并排序c.快速排序d.堆排序3. 设输入序列为字符a、b、c,则经过栈的作用后可以得到(c )种不同的输出序列。a.3b. 1c. 5d. 64. 数组a|7 |6的每个元素占5个字节.将其以行为主序存依在起始地址为100()的内存单元 中.则元素a 5 4的地址是< c )。a.1165b.1180c. 1170d.12105. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：()。a. o(n) , o(n) b. o(n) . 0(1) c. 0(1) . 0(1) d. 0(1) . o(n)6. 在单链

3、表指针为p的结点之后插入指针为，的结点，正确的操作是( b 九a. p->next=s： s->next=p->ncxtb. s->nexl=p->next： p->next=sc. p->ncx(=s： p->ncxt=s->ncxtd. p->ncxt=s->ncxt： p->ncxt=s7. n个顶点的有向图中，含有向边的数目最多为()。a n-1b. nc. n(n-l)/2d. n(n-l)8. 对下面有向图给出了四种可能的拓扑序列，其中错误的是(c ).a. l 5. 2, 6, 3, 4b,5, 6, 2.

4、3, 4c. 5, 1， 6， 3, 4, 2d. 5, l 2, 6, 4, 39. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则叶子结点数为(ba. 9 b. 11c. 15 d.不确定10. 适用于折半查找的表的存储方式及元素排列要求为()<>a顺序方式存饬，元素有序 b.顺序方式存储，元素无序c.链接方式存储.元素有序d.链接方式存储.元素无序二、填空题。(每空1分，共8分)1. 度量算法效率可通过时间复杂度和两方面进行。2. 迷宫问题是一个回溯控制的问我，最好使用_结构来记录路径数据。3. 设字符sl= abcde s2= aaa 则执行运j? strinse

5、rt(s 1. strlength(s2). s2)；sl=_'abaaacdc、:若串 s2 采用 sstring 存储结构，则 s20=4. 进行哈希查找的基木思想是由关蚀字决定记录的存储地址。5. 设某棵二叉树中有2000个结点，则该二叉树的最小深度为6. 采用顺序查找方法查找长度为n的表时，等概率情况卜的平均查找长度为：(nq 27. 在队列中存取数据的原则是。三、简答题。(每题6分，共12分)1 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。答：具有3个结点的树有2种形态：具有3个结点的二叉树有5种形态：2. 一个“好”的算法应考虑达到哪些目标？答：算法是对特

6、定问题求解步骤的种描述它是指令的有限序列。（2分 它的五个重要特性是:<1）有穷性：（2）确定性：（3）可行性：（4）零个或多个输入：四、应用题。（每题12分，共36分）1.已知图g如请回答以下问题:（d从顶点1出发,用普里姆算法构造最小生成树，请写出构树的逻辑步骤.wpl= (10+14) *2+ (6+7+8) *3+ (2+3) *4 =24*2+21*3+5*4=48+63+20=131(4 分)3.己知棵树的双亲表示法如下，回答以下问题:u= ,v.u=(23,45 tf>4>(1)u=1,2 ,v.u=3,4§ ,te=(1,2)(2)（每步2分，共8分

7、）u=1,2,4,5j ,v-u= <bte=(1,2),(1,4),(2,5),(5)u=*，、-u=3,5te=(1,2),(1,4)（2）写出图g的邻接矩阵。u=1,2,4,5 ,v.u=3te=(1,2),(1,4),(2,5)2.有7个带权站点.其权值分别为3. 7,8,2,6,10, 14：（i）画出以它们为叶子结点的哈夫曼树（树中左孩子结点的权值不大丁右孩子结点的权值）： 计算出带权路径长度wpl。解：哈夫曼树为:（8分）<2）写出该树的前序和后序遍历序列。 解：该树的前序遍历序列：abefcgdh （2分）五、算法阅读题。（共14分）1 .假设以带头结点的单链表表示

8、线性表.阅读卜列算法fl,并回答问题:void fklinklist l） （p=l;while （p && p->next）q = p->next;2129p->next =q->next; p =q->next; fnre(|);设单链表 l 为：e4|h al a2 a3 « a4 a5 一 a6 “卜7 囚 清画出执行fl(l)；后的单链表l：e*1riirn*i 孩41 bn亦|(6 分)2.算法f2功能：在有序表st中折半查找关键字等于key的数据元素，请叵i答卜列问题：int f2(<istab!c st, keytype key) low=l; high=st.length;while (low<=high) (mid= (l»w+hmh) /2:if ( key=st.elem|mid|.key)return mid;else if (key< slelemmid.key) high=mid-l;else low=mid+l;return 0;)(i)请完成算法填空。(每空2分，共8分)六、算法设计题。(共10分)1.以顺序存储结构表示线性表，编写算法，求出线性表中元素的址大值。函数原型为：status s(