数据结构考试样卷

《数据结构考试样卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、河北大学课程考核试卷—学年第学期级专业（类）考核科目数据结构课程类别必修课考核类型考试考核方式闭卷卷别（注：考生务必将答案写在答题纸上，写在本试卷上的无效）一、单项选择题（共20分，每题2分）1、线性表采用链式存储时，结点的存储地址（）A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址相连续2、下列说法不正确的是（）A、栈是一种运算受限的线性表B、栈是一种后进先出的线性结构C、栈可以是线性结构也可以是非线性结构D、栈可以用数组实现或链表来实现3、设循环队列中数组的下标范围是0～n-1，f表示队首元素的前驱位置，r表示队尾元素的位

2、置，则队列中元素个数为（）。A、r-fB、r-f+1C、(r-f+1)modnD、(r-f+n)modn4、一棵度数为4的树，它的4度结点有1个，3度结点有2个，2度结点有3个，1度结点有4个，问它的叶子结点有多少个？（）A、5B、6C、9D、115、在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（）A、eB、2eC、n2-eD、n2-2e6、已知一个有向图如右所示，则从定点a出发进行深度优先遍历，不可能得到的DFS序列为（）A、adbefcB、adcefbC、adcbfeD、adefcb7A-5-5、一棵深度为k的平衡二叉树，其每个非终端

3、结点的平衡因子均为0，则该树的共有（）个结点。A、1B、C、D、8、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。A、无序 B、中序 C、后序 D、从根开始的层次遍历9、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。A、0(n)B、0(log2n) C、0(nlog2n) D、0(n2)10、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 

4、       20，15，21，25，47，27，68，35，84        15，20，21，25，35，27，47，68，84        15，20，21，25，27，35，47，68，84则所采用的排序方法是（  ）A、选择排序    B、 归并排序   C、快速排序    D、希尔排序二、填空题（共18分，每空1分）1、在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：①和②。2、若一个算法中的语句频度之和为T(n)=3720n+4nlogn，则算法的时间复杂度为③。3、假设以S和X分别表示进栈和退栈操作，

5、则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为④。4、一个高度为h的二叉树，至少有⑤个结点，至多有⑥个结点。5、具有9个结点的完全二叉树中有⑦叶子结点。A-5-56、有n个结点并且高度为n的二叉树的数目是⑧。7、线索二叉树中,某结点*p没有孩子结点的充要条件是⑨且⑩。8、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是⑪条。9、一棵哈夫曼树有19个结点，则其叶子结点的个数是⑫。10、对一个连通的网图，求其最小生成树时，顶点多而边少时宜使用⑬方法，顶点少而边多时宜使用⑭方法。11、6阶B树中，每个结

6、点至多包含⑮个关键码，除根和叶结点外，每个结点至少包含⑯个关键码。12、折半查找的存储结构仅限于⑰且是⑱。三、算法填空（共6分，每空2分）设A,B分别为两个带头结点单链表的头指针,且两表中结点的数据集均为整数集合,下面算法产生两表中数据的交集,并以表c存储之(即c为结果表的头指针).请填充算法中下面线的空白处,完成其功能.Typedefstructnode{intdata;structnode*next;}lnode,*link;linkandset(linkA,linkB){linkC,r,p,q,s;C=r=(link)malloc(sizeof

7、(lnode));q=Bànext;while(q!=NULL){p=Aànextwhile(①){if(pàdata=qàdata){s=(lnode*)malloc(sizeof(lnode));A-5-5sàdata=pàdata;②;r=s;break;}③;}//whileq=qànext;}//whilerànext=NULL;return(C);}}四、应用题（共36分，每小题6分）1、已知一棵二叉树如下图所示，写出此二叉树的的中序遍历序列和后序遍历序列。2、已知一图如下图所示，用Prim算法求其最小生成树，要求分步骤写出求解过程。A-

8、5-53、将下图所示的树转换成二叉树，要求分步骤写出求解过程。4、给定权值7，18，3，32，5，26，12