2007—2008_学年第2学期《数据结构》考试试卷(a卷)

《2007—2008_学年第2学期《数据结构》考试试卷(a卷)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽大学2007—2008学年第二学期《数据结构》考试试卷（A卷）（闭卷时间120分钟）一、单项选择题（每小题1，共10分）1．算法分析的目的是。A．找出数据结构的合理性B．分析算法的正确性C．分析算法的时间和空间效率D．分析算法的可读性2．带头结点的单链表head为空的条件是。A．head==NULLB．head→next==NULLC．head→next==headD．head！=NULL3．栈和队列的共同点是。A．先进先出B．后进先出C．只能在一端进行插入和删除D．限制存取点的线性表4.在数组A中,每个

2、元素占3个字节,行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器中,该数组按列存放时,元素A[8][5]的起始地址为。A．SA+117B．SA+120C．SA+144D．SA+1415．广义表（（a,b），c,d）的表头是。A．aB．（a）C．（a,b）D．（（a））6．若某二叉树的中序序列为dgbaechf，后序序列为gdbehfca，则先序序列是。A．abdgcefhB．gdbecfhaC．adbehfcgD．abdgechf7．若一棵哈夫曼树的结点总数为2001个，则它有（）叶子结

3、点。A．999B．1000C．1001D．10028．已知有向图的邻接表如下所示，从顶点v1出发，得到的DFS序列为。A．V1，V2，V3，V4，V5B．V1，V2，V3，V5，V4C．V1，V3，V4，V5，V2D．V1，V4，V3，V5，V21324∧2∧345∧4∧524∧9．折半查找法适合于存储结构为的线性表。A．顺序存储B．散列存储C．二叉树D．链式存储10．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用。A．冒泡排序法B．快速排序法C．堆排序法D．插入排序法二、填

4、空题（每题1分，共10分）1．下面程序段中语句x++的执行次数是。for（i=1；i＜n；i++）{y=y+1；for（j=0；j＜=2*（n+1）；j++）x++；}2．在单链表L中设立头结点的作用是。3．一个栈的输入序列为1，2，3，4，得到的输出序列4，1，2，3是的。4．引入循环队列的目的是。5．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置，这种说法是。6．广义表的表尾是广义表，这种说法是。7．根据二叉树的定义，n个结点的二叉树的不同形态有。8．图的DF

5、S和BFS遍历得到的结点序列不唯一，与有关。9．用二叉排序树查找，在最坏情形下的性能时间与相同。10．已知序列{54，38，96，23，15，72，60，45，83}，采用直接插入排序，将60插入到有序子区间时，为寻找插入位置需比较次。得分得分三、分析应用题（每题5分，共20分）1．阅读以下算法，按要求回答问题。func（inta[]，intn，intx）{inti，j；if（x>=a[n-1]）a[n]=x；else{i=0；while（x>=a[i]）i++；for（j=n-1；j>=i；j--）a[j+

6、1]=a[j]；a[i]=x；n++；}returnn；}该算法的功能是。2．写出以下程序段的输出结果（队列中的元素类型为char，EnQueue（Q，x）表示元素x进队Q，DeQueue（Q，x）表示队头元素出队后保存在x中）voidmain（）{charx=’e’,y=’c’;EnQueue（Q，’h’）;EnQueue（Q，’r’）;EnQueue（Q，y）;DeQueue（Q，x）;EnQueue（Q，x）；DeQueue（Q，x）；EnQueue（Q，’a’）;while(!QueueEmpty(Q

7、){DeQueue（Q，y）;printf(y);}Printf(x);}3、对于如下的连通图，请给出从顶点0出发，利用普里姆（Prim）算法画出它的最小生成树。054163268151349201051612124、设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。GEDCFBAIJHLMKT1T2T3森林四、解答题（每题10分，共40分）1．已知二叉树的顺序存储结构如下图所示：1234567891011121314151617181920eafdgcjhib⑴画出二叉

8、树T的逻辑结构图；⑵写出按先序、中序和后序遍历T所得到的结点序列；⑶画出后序线索树。2．已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示(1)画出该图的图形；(2)根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。3．设下列关键字构造哈希表（hash）表，的地址范围为0~17，关键字序列为10，24，32，17，31，30，46，47，40，63，49，⑴