《内蒙古大学2008～2009 学年第二学期算法与数据结构试卷(A卷)及参考答案》由会员分享，可在线阅读，更多相关《内蒙古大学2008～2009 学年第二学期算法与数据结构试卷(A卷)及参考答案（11页珍藏版）》请在金锄头文库上搜索。
1、第 1页共 8 页计算机学院计算机学院 2007 级级 2008200820092009 学年第二学期学年第二学期算法与数据结构试卷算法与数据结构试卷(A(A 卷卷) )（闭卷 120120 分钟）班级姓名学号重修标记总分题号一二三四五核分人得分复查人得分一、一、单项选择题单项选择题（在每小题的四个备选答案中在每小题的四个备选答案中，选出一选出一个正确的答案，并将其号码填在题干中的括号内。本个正确的答案，并将其号码填在题干中的括号内。本大题共大题共 1010 小题，每小题小题，每小题 2 2 分，共分，共 2020 分）分）1. 向一个有 127 个元素的顺序表中插入一个新元素，平均要移动（）
2、个元素(假定每个位置插入的概率都相等）。A.8B.63.5C.63D.642.在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是（）。A. p-next=headB. p-next-next=headC. p-next=NULLD. p=head3. 设有一个二维数组Amn， 假设A00存放位置在644， A22存放位置在676，每个元素占一个字节，则 A45在（）位置。A. 692B.626C.709D. 7244. 设有一个顺序栈 S，元素 s1， s2， s3， s4， s5， s6 依次进栈，如果 6 个元素的出栈顺序为 s2， s3， s4， s6， s
3、5， s1，则顺序栈的容量至少应为()。A.2B.3C.4D.55. 在一个具有 n 个顶点的有向图中，所有顶点的出度之和为 Sum ，则所有顶点的入度之和为（） 。A.nB.Sum-1C.Sum+1D.Sum6. 已知用某种排序方法对关键字序列（51，35，93，24，13，68）进行排序时，前两趟排序的结果为（13，51，35，93，24，68）和（13，24，51，35，93，68）所采用的排序方法是（）。A. 直接插入排序B. 冒泡排序C. 快速排序D. 归并排序得分得分评卷人评卷人装订线第 2页共 8 页7. 已知一棵含 50 个结点的二叉树中只有一个叶结点， 则该二叉树中度为 1
4、的结点个数为（）.A. 0B. 1C. 48D. 498. 某二叉树的前序遍历和后序遍历序列正好相同， 则该二叉树一定是 （） 的二叉树。A. 空或只有根结点B. 高度等于其结点数C. 任一结点无做孩子D. 任一结点无有孩子9. DFS 算法的时间复杂度为（）。A. O(n)B. O(n2)C. (n3)D. O(n+e)10. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O(logn)的是（）。A. 直接选择排序B. 冒泡排序C. 堆排序D.快速排序二、二、填空题（本大题共填空题（本大题共 1313 小题，每空小题，每空 1 1 分，共分，共 2020 分）分）11. 数据元素是。
5、数据项是。12. 算法除了具有输入和输出特性之外， 还具有、和特性。13. 队列是特殊的线性表， 它的特殊性在于。14. 将对称矩阵 Ann中进行按行优先顺序压缩存储在一维数组 B中时，元素 Aij(0ijn-1) 在 B 中的下标为。15. 二叉树一共有种形态。16. 在 K(K2)叉树中的第 i 层上最多有个结点（设根在第 1 层） 。17. 在对二叉查找树进行中序遍历时，遍历序列中关键码。18. 对图进行深度优先遍历和广度优先遍历时，算法中用到的关键数据结构分别为和。19.AOE 的含义是。AVL 的含义是。20. 快速排序算法在最坏情况下和平均情况下的时间复杂度分别为和。21. 希尔排
6、序是对排序的改进。22. 若有向图中顶点数为 n，弧数为 e，则用邻接矩阵表示有向图时，有个数据元素，有个非零元素。23. 链接存储的特点是利用来表示数据元素之间的逻辑关系。得分得分评卷人评卷人第 3页共 8 页三、三、解答题解答题（本大题共本大题共 4 小题小题，每小题每小题 5 分分，共共 20 分分）24. 设一棵二叉树的前序序列、中序遍历分别为 DBACFEG 和 ABCDEFG。请画出这棵二叉树，并给出后序遍历序列。25. 请给出一种在循环队列中，解决队空和队满的方案。得分得分评卷人评卷人装订线第 4页共 8 页26. 简述下列算法的功能。intexam1 (BinTreeNode*
7、root ) if ( !root ) return 0;elsereturn 1 + Max (exam1 ( rootleftChild ), exam1 ( rootrightChild ) );其中：Max(a,b)函数是求 a,b 的最大值。27. 请写出下列稀疏矩阵按行优先顺序压缩存储时的三元组表示。 15000900000012022000000000017230000003500A第 5页共 8 页四、四、算法应用题（本大题共算法应用题（本大题共 3 小题，第小题，第 28 小题小题 6 分，分，第第 29 小题和第小题和第 30 小题各小题各 7 分，分， 共共 20 分）分
8、）28. 请问序列 81，52，57，22，95，04，83，96，42，32 是否为最大堆？若不是，请调整为最大堆。29.利用 Dijkstra 算法求下图带权有向图中从顶点 V0 到其它顶点的最短路径和长度。得分得分评卷人评卷人装订线第 6页共 8 页30. 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题：（1）设线性表 L=（21，-7，-8，19，0，-11，34，30，-10），写出执行 exam(&L)后的 L 状态；（2）简述算法 exam 的功能。voidexam(SeqList*L) inti, j;for (i=j=0;ilength; i+)if(L-datai=
9、0)if(i!=j)L-dataj=L-datai;j+；L-length=j;(1)(2)第 7页共 8 页五、算法题（本大题共五、算法题（本大题共 2 2 小题，每小题小题，每小题 1010 分，共分，共 2020 分）分）31. 编写一个向二叉查找树中插入一个元素的 insert()算法。其中二叉查找树是以二叉链表存储的，说明如下：class BinaryTreeNodeDataType data;/数据元素BinaryTreeNode *leftChild, *rightChild;/左指针，右指针public :void insert(BtreeNode * BST, DataTyp
10、e &item)/插入算法;得分得分评卷人评卷人装订线第 8页共 8 页32. 下面是将中缀表达式转为后缀表达式的算法，每个操作数以字母表示，运算符集合为op#，+，-，*，/，(，)。其中#优先级最小，其它运算符的优先级遵循数学中的四则运算。从键盘输入中缀表达式，把转换后的后缀表达式向屏幕显示。请阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。其中：compare(ch1,ch2)函数功能是比较 ch1 和 ch2 优先级的大小，如 ch1 小于 ch2，函数返回，如等于，函数返回=。void postexpression( )char ch;Stack s;ch=getchar
11、();s.Push(#);while(ch!=# | s.GetTop()!=#)if(!In(ch,op) / In(ch,op)函数功能是判断 ch 是否属于集合 op。putchar(ch);elseswitch(compare(s.GetTop(), ch) case :;break;case =:;ch=getchar();break;并根据算法，将中缀表达式 A*(B+C)-D/F# 转为后缀表达式。第 10页共 8 页一一、 单单项项选选择择题题（本本大大题题共共 1 10 0 小小题题，每每小小题题 2 2 分分，共共 1 10 0 分分）12345678910BACBDBDA
12、DC二二、填填空空题题（本本大大题题共共 1 13 3 小小题题，每每空空 1 1 分分，共共 2 20 0 分分）11数据的基本单位数据元素不可再分的最小单位12有穷性可行性确定性13在表的一段进行插入，而在另一端进行删除或先进先出14j*(j+1)/2+i15516.ki-117从小到大排序18栈队列19Activity On Edge高度平衡的二叉查找树20.O(n2)O(nlogn)21. 直接插入排序22. n2e23. 指针三三、解解答答题题（本本大大题题共共 4 小小题题，每每小小题题 5 分分，共共 20 分分）24.后序遍历序列为：ACBEGFD25. 方案 1: 在能放 m
13、 个元素的循环队列中，最多允许放 m-1 个元素。这样队空时：rear=front队满时：(rear+m)%m=front方案 2:给队列设一个标志位以区别队列是空还是满；方案 3:是给队列增加一个统计元素个数的变量 count，当 count=m 时队满；count=0 时队空；任选其一解决即可。2 26.求二叉树的高度或深度。DBFACEG本科课程考试试题参考答案及评分标准第 11页共 8 页27.四四、算法应用题算法应用题（本大题共本大题共 3 小题小题，第第 28 小题小题 6 分分，第第 29 小题和第小题和第 30 小题各小题各 7 分分， 共共 20 分分）28. 不是调整后的最
14、大堆为：29.1234512345201500000171520000171527472011017152747422011417152747422011430. （1）L=（21，19，0，34，30）（2）删除线性表 L 中小于 0 的元素，其它元素依次前移。ijvalue0124466240130435231722-12-915distpath第 12页共 8 页五、算法题（本大题共五、算法题（本大题共 2 2 小题，每题小题，每题 1010 分，共分，共 2020 分）分）31. void insert(BtreeNode * BST, DataType &item) BtreeNode *p=BST, q=NULL;while(p) if(p-dataitem) q=p;p=p-leftChild; elseif(p-datarightChild; else return;BtreeNode *s=new BtreeNode(item);if(!BST)BST=s;else if(q-dataitem)q-leftChild=s;else q- rightChild=s;32. ch=getchar();s.Push(ch);putchar(ch);s.Pop();
