西南民族大学数据结构考试模拟卷答案 1.docx

1、西南民族大学数据结构考试模拟卷答案 1题号一二三四五六七八九十总分得分一、请判断下列说法的是否正确:(10分）(1）若某堆栈的输入序列为1，2,3，4,则4,3,1，2不可能是堆栈的输出序列之一。（ ）（2）队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（ ）（3）若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点.（ ）（4）在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关,而与每块中元素个数无关。( )（5）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值,小于其右孩子的值。( ）（6）在10万

2、个随机排列的数据中，要选出5个最小的数，采用快速排序比采用Shell排序、堆排序及各种直接排序法都快。（ ）（7）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关.（ ）. （8）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ ）（9）二分查找法不仅适用于顺序存储的有序表，而且适合于链接表。（ ）（10）按中序遍历一棵二叉排序树所得到的遍历序列是一个递增序列.（ ）二、填空(20分)(1）数据结构有如下四种基本结构： 、 、 、 。 （2）在一个算法中的语句频度之和为T（n）=3720n+4nlogn,则算法的时间

3、复杂度为 .（3） 已知某二叉树的叶子结点的个数为10个，度为1的结点个数为8个,则该二叉树的结点总数为： 个。（4） 已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分检索值为90 的元素时，需_ _次比较可检索成功.（5)、图的遍历方法主要有两个,一个是 ,另一个是 。(6) 在哈希造表过程中，处理冲突的方法主要有： ， , ， 。(7）在一个单链表中p所指结点（p所指不是最后结点）之后插入一个由指针s所指结点，应执行snext=_ _；和p-next=_ _的操作。(8）。已知一棵二叉树的先序序列为ABCD，中序序列为BCAD，则它的后序序列

4、为_ _。 (9）有N个顶点组成的无向连通图，最多可以_条边。（10）、若某序列的初始状态为49，13，42，8,65，55，79，若以49为枢轴，则经过一趟快速排序之后的序列为： 。三、单项选择题(每小题2分,共20分）1从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动（ ）个元素。A）. n-i B）。 n-i+1 C）. n-i1 D）。 i2)、队列操作的原则是:（ ) A）先进先出 B)后进先出 C)只能进行插入 D)只能进行删除 3）下列算法中，( )算法用来求图中每对顶点之间的最短路径。A）Dijkstra B）Floyed C）Prim D)Kruskal4、下面

5、关于线性表的叙述中，错误的是 （ ）A）线性表采用顺序存储，必顺占用一片连续的存储单元。 B）线性表采用顺序存储,便于进行插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元 D)线性表采用链接存储，便于插入和删除操作。5、对下面的有向图进行拓扑排序，其排序结果不正确的是：( ）。 A） 1、4、2、6、5、3 B )1、2、4、6、3、5 C） 1、4、2、5、6、36、带头结点的单链表head为空的判定条件是：（ )A)head= =NULL B。) head-next= =NULL C）、。headnext= =head D）.head！=NULL7、在所有排序方法中,关

6、键字的比较次数与记录的初始排列无关的是_。 A） Shell排序 B） 冒泡排序 C。) 直接插入排序 D) 直接选择排序8、设有两个串p和q，求q在p中首次出现的位置的运算叫_。 A）。 模式匹配 B)。 求子串 C.） 定位 D）。 查找9、将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度为(）A。） O(m) B.) O（1) C.） O(n) D ). O（m+n) 10、用线性探测法查找散列表，可能要探测多个散列地址，这些位置上的关键值（ ） A。） 一定都是同义词 B)。 一定都不是同义词 C）。 都相同 D）不一定都是同义词四、解答题(3分）、对于给定的一组权值，,

7、画出Huffman树（要求结点左小右大），并给出每个结点的Huffman编码，计算该树的WPL.(6分）2、考虑下图：（0分）1）从顶点出发，求它的深度优先生成树。2）从顶点出发，求它的广度优先生成树。3）根据普里姆(rim)算法，求它的最小生成树。（从顶点A出发，要求给出计算过程） 3、已知待散列的线性表为(36，15，40，63，22），散列用的一维地址空间为0.。6，假定选用的散列函数是H（K）=K 7，若发生冲突采用线性探查法处理,试：（1）计算出每一个元素的散列地址并在下图中填写出散列表；（2）求出在查找每一个元素概率相等情况下的平均查找长度.（6分）01234564、对关键字序列（

8、49,38,65,97，76,13，27，49）进行堆排序，使之按关键字非递增次序排列.请写出排序过程中得到的初始堆和前二趟的序列状态. （8分)初始堆:_ 第1趟：_ _ 第2趟：_ _ 五、算法填空与设计（20分）1、此为向以T为树根指针的二叉排序树上插入值为item的结点的递归算法.（6分）void Insert（BiTree T， ElemType item) if（T=NULL） p=( BiTree ）malloc（sizeof(BiTNode)）; p-data=item； _; T=p; else if（item.keyT-data.key) _; else _； 其中:二叉树

9、的存储结构为：typedef struct BiTNode ElemType data; Struct BiTNode *lchild， rchild;BiTNode, Bitree；2、以下运算实现在循环队上的入队列,请在_处用适当句子予以填充。(6分）status EnQueue（SqQueue Q, QElemType x）/插入元素x为Q的新的队尾元素 if(（Q。rear+1)MAXQSIZE= _) error（“队满”); return(ERROR); else _; _; return（OK）； 其中循环队列存储结构为:define MAXQSIZE 100 typedef s

10、truct QelemType *base; int front；int rear； SqQueue；3、已知一个线性表中的元素按元素值非递减有序排列,编写一个程序删除线性表中多余的值相同的元素，并返回删除后线性表的长度（8分)一( 每小题1分：）1正确 2、错误 3、正确 4、错误 5、错误6、错误7正确、8、正确9、错误10、正确二、每小题2分1、集合、线性结构、图结构、树结构2、O（nlogn）3、274、2次5、 深度优先搜索,广度优先搜索6、1、开放地址法 2、再哈希法 3、链地址法 4、建立一个公共的溢出区7、s-next=pnext pnext=s；8、CBDA9、1/2N*(N

11、1）10、8 13 42 49 65 55 79三、每小题2分A A B B C B D A A D四、1）19：00 9：010 3：0110 6:0111 11：100 13:10115：110 17：111；WPL=（192+93+34+64+11*3+133+15*3+173）=2692、1）（有多种答案) 2）(有多种答案）3）(计算过程略)3、 （1） H（36）=36 % 7=1 H（15）=15 7=1 冲突 H1（15）=（15+1) % 7=2 H(40）=40 7=5 H（63）=63 7=0 H（22）=22 % 7=1 冲突 H1（22)=(22+1） 7=2 冲突

12、H2(22）=（22+2）%7=301234566336152240 (2）平均查找长度=（1+2+1+1+3）/5=1.64、初始堆：13，38，27，49,76，65，49，97 第一趟：27，38，49，49,76,65，97，13 第二趟;38，49，49，97，76，65,27，13 五、1）plchild=NULL;p-rchild=NULL；2) Insert(T-lchild，item）； 3） Insert(Trchild，item)4 ） =Q。front 5） Q.baseQ.rear=e; 6) Q.rear=（Q。rear+1)MAXQSIZE;3、（8分）typedef struct ElemType *elem；int length;int listsize； SqList；int del（SqList A） int i=0, j； while (i=A。length1） if (A。elemi!=A。elemi+1） i+; else for (j=i; jA.length； j+） A.elemj=A.elemj+1； A.length-； return A.length；