数据结构考试样卷.doc

河 北 大 学 课 程 考 核 试 卷 学年 第 学期 级 专业（类）考核科目 数据结构 课程类别 必修课 考核类型 考试 考核方式 闭卷 卷别 （注：考生务必将答案写在答题纸上，写在本试卷上的无效）一、单项选择题（共20分，每题2分）1、线性表采用链式存储时，结点的存储地址（ ） A、必须是不连续的 B、连续与否均可C、必须是连续的 D、和头结点的存储地址相连续2、下列说法不正确的是 （ ）A、栈是一种运算受限的线性表 B、栈是一种后进先出的线性结构 C、栈可以是线性结构也可以是非线性结构 D、栈可以用数组实现或链表来实现3、设循环队列中数组的下标范围是0 n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为（ ） 。A、r-f B、r-f+1 C、(r-f+1)mod n D、(r-f+n)mod n4、一棵度数为4的树，它的4度结点有1个，3度结点有2个，2度结点有3个，1度结点有4个，问它的叶子结点有多少个？（ ）A、5 B、 6 C、 9 D、 115、在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（ ）A、e B、 2e C、 n2-e D、 n2-2e6、已知一个有向图如右所示，则从定点a出发进行深度优先遍历，不可能得到的DFS序列为 （ ） A、 adbefc B、 adcefb C、 adcbfe D、 adefcb 7、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树的共有（ ）个结点。A、1 B、 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）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，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分别表示进栈和退栈操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为 。4、一个高度为h的二叉树，至少有 个结点，至多有 个结点。5、具有9个结点的完全二叉树中有 叶子结点。6、有n个结点并且高度为n的二叉树的数目是 。7、线索二叉树中,某结点*p没有孩子结点的充要条件是 且 。8、在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是 条。9、一棵哈夫曼树有19个结点，则其叶子结点的个数是 。10、对一个连通的网图，求其最小生成树时，顶点多而边少时宜使用 方法，顶点少而边多时宜使用 方法。11、6阶B树中，每个结点至多包含 个关键码，除根和叶结点外，每个结点至少包含 个关键码。12、折半查找的存储结构仅限于 且是 。三、算法填空（共6分，每空2分）设A,B分别为两个带头结点单链表的头指针,且两表中结点的数据集均为整数集合,下面算法产生两表中数据的交集,并以表c存储之(即c为结果表的头指针).请填充算法中下面线的空白处,完成其功能.Typedef struct node int data;struct node *next;lnode,*link;link andset(link A,link B) link C,r,p,q,s;C=r=(link)malloc(sizeof(lnode);q=Bnext;while( q!=NULL ) p=Anextwhile( ) if(pdata=qdata) s=(lnode *)malloc(sizeof(lnode);sdata=pdata; ;r=s; break; ;/whileq=qnext;/whilernext=NULL;return(C); 四、应用题（共36分，每小题6分）1、已知一棵二叉树如下图所示，写出此二叉树的的中序遍历序列和后序遍历序列。2、已知一图如下图所示，用Prim算法求其最小生成树，要求分步骤写出求解过程。3、将下图所示的树转换成二叉树，要求分步骤写出求解过程。4、给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树，要求分步骤写出求解过程。5、对于下列一组关键字46，58，15，45，90，18，10递增排序，写出冒泡排序每一趟的排序结果。6、设关键码序列为47，29，11，16，22，8，3，50，37，94，21，选取哈希函数为Hash(key)=key mod 11，将关键码序列填入010共11个地址空间中，使用线性探测法解决冲突并给出各个关键码发生冲突的次数。五、程序设计题（共20分，每小题10分）要求：简述算法思想