数据结构模拟卷(含答案)经典习题(19页).doc

《数据结构模拟卷(含答案)经典习题(19页).doc》由会员分享，可在线阅读，更多相关《数据结构模拟卷(含答案)经典习题(19页).doc（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构模拟卷(含答案)经典习题-第 19 页练习题一、单项选择题1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合 D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1in)时，元素移动的次数为( )A. n-i+1 B. iC. i+1 D. n-i3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( )A. head=NULL B. head-next=NULLC. head!=NULL D. head-next=head4. 引起循环队列队头位置发生变

2、化的操作是( )A. 出队 B. 入队C. 取队头元素 D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )A. 2，4，3，1，5，6 B. 3，2，4，1，6，5C. 4，3，2，1，5，6 D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是( )A. 散列存储和索引存储 B. 索引存储和链式存储C. 顺序存储和链式存储 D. 散列存储和顺序存储7. 数据结构是（）A一种数据类型B数据的存储结构C一组性质相同的数据元素的集合D相互之间存在一种或多种特定关系的数据元素的集合8. 算法分析的目的是（）A辨别数据结构的合

3、理性B评价算法的效率C研究算法中输入与输出的关系D鉴别算法的可读性9. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（）A插入B删除C排序D定位10. 下列图示的顺序存储结构表示的二叉树是( )11. 设串sl=Data Structures with Java,s2=it，则子串定位函数index(s1,s2)的值为(）A15B16C17D1812. 二维数组A89按行优先顺序存储，若数组元素A23的存储地址为1087，A47的存储地址为1153，则数组元素A67的存储地址为（）A1213B1209C1211D120713. 在按中序遍历二叉树的算法中，需要借助的辅助数据结构是（

4、）A队列B栈C线性表D有序表14. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）A不一定相同B都相同C都不相同D互为逆序15. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A层次遍历算法B前序遍历算法C中序遍历算法D后序遍历算法16. 若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目17. 图的邻接矩阵表示法适用于表示（）A无向图B有向图C稠密图D稀疏图18. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进

5、行比较的关键字依次为（）Af,c,bBf,d,bCg,c,bDg,d,b19. 下面程序段的时间复杂度为( ) s=0； for(i=1；in；i+) for(j=1；jnext=s-next；s-next=p；B.s-next=p；q-next=s-next；C.p-next=s-next；s-next=q；D.s-next=q；p-next=s-next；21. 在计算机内实现递归算法时所需的辅助数据结构是( )A.栈B.队列C.树D.图22. 通常将链串的结点大小设置为大于1是为了( )A.提高串匹配效率B.提高存储密度C.便于插入操作D.便于删除操作23. 带行逻辑的三元组表是稀疏矩阵

6、的一种( )A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构24. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为( )A.n-1B.nC.n+lD.2n25. 为便于判别有向图中是否存在回路，可借助于( )A.广度优先搜索算法B.最小生成树算法C.最短路径算法D.拓扑排序算法26. 连通网的最小生成树是其所有生成树中( )A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树27. 按排序过程中依据的原则分类，快速排序属于( )A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法28. 在长

7、度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为( )A.4B.5C.6D.729. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为( )A.n-1B.nC.n+lD.n+230. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）Af,c,bBf,d,bCg,c,bDg,d,b二、填空题1. 数据的逻辑结构在计算机存储器内的表示，称为数据的_。2. 已知双向循环链表结点中，域prior指向前一结点，域next指向后一结点，

8、则删除当前结点指针p的前驱结点(存在)应执行的语句是_。3. 栈下溢是指在_时进行出栈操作，栈上溢是指在_时进行入栈操作。4. 已知substr(s,i,len)函数的功能是返回串s中第i个字符开始长度为len的子串，strlen(s)函数的功能是返回串s的长度。若s=”ABCDEFGHIJK,t=”ABCD,执行运算substr(s,strlen(t), strlen(t)后的返回值为_。5. 已知完全二叉树T的第5层只有7个结点，则该树共有_个叶子结点6. 在有向图中，以顶点v为终点的弧的数目称为v的_,以顶点v为源点的弧的数目称为v的_。7. 假设以数组seqnm存放循环队列的元素，设变

9、量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。写出一般情况下队头元素位置的表达式。如果用变量front和quelen分别指示循环队列中队头元素的位置和元素的个数，则写出一般情况下队尾元素位置的表达式。8. 已知二叉树如下，写出它的先序序列、中序序列和后序序列BFGDCEA9. 称算法的时间复杂度为O(f(n)，其含义是指算法的执行时间和_的数量级相同。10. 在一个长度为n的单链表L中，删除链表中*p的前驱结点的时间复杂度为_，删除*p结点的时间复杂度为_。11. 假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为_。12

10、. 一棵含999个结点的完全二叉树的深度为_,深度为10的满二叉树有_个结点。13. 含n个顶点的无向连通图中至少含有_条边。14. .已知有向图G的定义如下： G=(V，E) V=a，b，c，d，e E=， ， (1)画出G的图形； (2)写出G的全部拓扑序列。15. 线性表的链接存储比顺序存储的优点是：_操作不需移动结点。16. 孩子兄弟链表表示的树结构，其后根遍历结果同二叉树的_.一致。17. 哈夫曼树又称_.其定义是_18 队列是一种_线性表，而栈是_线性表。19. 画出与如图所示森林对应的二叉树。20.下列线索化的树称为_，画出中序线素二叉树的线索表示。BACDEFGH21. 填写语

11、句完成对顺序表的初始化#define LIST_INIT_SIZE 100typedef struct ElemType *elem; /存储空间起始地址int length; /线性表长度int listSize; /分配容量 SqList;Status initList_Sq(SqList &l)l.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!l.elem) exit ERROR;_;_;return OK;22.一般而言，若二叉树的结点，其左子树的所有结点小于根结点，而右子树的所有结点大于根结点，则二叉树称为_

12、; 如果结点的左子树深度和右子树深度之差的绝对值不超过1，则二叉树称为_.三、解答题1. 已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；（2）画出与（1）求得的二叉树对应的森林。2. 从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。（1）画出该二叉排序树；（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。3. 已知用有序链表存储整数集合的元素。阅读算法f3，并回答下列问题：（1）写出执行f3（a,b）的返回值，其中a和b分别为指向存储集合2，4，5，7，9，12和2，4，5，7，9,

13、 12的链表的头指针；（2）简述算法f3的功能；（3）写出算法f3的时间复杂度。 int f3(LinkList ha,LinkList hb) /LinkList是带有头结点的单链表 /ha和hb分别为指向存储两个有序整数集合的链表的头指针 LinkList pa,pb; pa=ha-next; pb=hb-next; while(pa & pb & pa-data=pb-data) pa=pa-next;pb=pb-next; if(pa=NULL & pb=NULL) return 1; else return 0;4. 已知稀疏矩阵采用三元组表表示，其形式说明如下： #define M

14、axSize 100/稀疏矩阵的最大行数 typedef struct int i,j,v;/行号、列号、元素值TriTupleNode; typedef structTriTupleNode dataMaxSize;int m,n,t;/矩阵的行数、列数和非零元个数RTriTupleTable;下列算法f4的功能是，以行优先的顺序输入稀疏矩阵的非零元（行号、列号、元素值），建立稀疏矩阵的三元组表存储结构。请在空缺处填入合适内容，使其成为一个完整的算法。（注：矩阵的行、列下标均从1起计）void f4(RTriTupleTable &R) int i,k;scanf(%d %d %d,&R-m

15、,&R-n,&R-t);k=1; /k指示当前输入的非零元的行号for(i=0; ；i+) scanf(%d %d %d, ， ，_;5. 已知二叉树的存储结构为二叉链表，其类型定义如下：typedef struct NodeType DataType data; struct NodeType *lchild,*rchild; BinTNode,*BinTree;阅读算法f5，并回答下列问题：(1)对于如图所示的二叉树，画出执行算法f5的结果；（2）简述算法f5的功能。BinTree f5(BinTree bt1) BinTree bt2; if(bt1=NULL) bt2=NULL; el

16、se bt2=(BinTNode *)malloc(sizeof(BinTNode); bt2-data=bt1-data; bt2-rchild=f5(bt1-lchild); bt2-lchild=f5(bt1-rchild); return bt2;6. 已知图的邻接表表示的形式说明如下：#define MaxNum 50 /图的最大顶点数typedef struct node int adjvex; /邻接点域 struct node *next; /链指针域 EdgeNode; /边表结点结构描述typedef struct char vertex; /顶点域 EdgeNode *f

17、irstedge; /边表头指针 VertexNode; /顶点表结点结构描述typedef struct VertexNode adjlistMaxNum; /邻接表 int n, e; /图中当前的顶点数和边数 ALGraph; /邻接表结构描述 下列算法输出图G的深度优先生成树(或森林)的边。阅读算法，并在空缺处填入合适的内容，使其成为一个完整的算法。typedef enum FALSE, TRUE Boolean;Boolean visitedMaxNum;void DFSForest(ALGraph *G) int i; for(i=0;in;i+) visitedi= (1) ;

18、for(i=0;in;i+) if (!visitedi) DFSTree(G,i);void DFSTree(ALGraph *G, int i) EdgeNode *p; visitedi=TRUE; p=G-adjlisti. firstedge; while(p!=NULL) if(!visitedp-adjvex) printf(,G-adjlisti. vertex, G-adjlistp-adjvex. vertex); (2) ; (3) ;参考答案二。填空题1. 存储结构（或存储映像）2. p-prior=p-prior-prior;p-prior-next=p;3.栈空，栈

19、满4.”DEFG”5.116. 入度,出度7. 队尾元素：（rear-quelen+1+m）% m队头元素：(front+quelen-1)%m8. 后序序列：BDCEGFA9. f(n)10. O(n),O(1)11. 1012. 10，102313. n-114.abecd,aebcd,eabcd15. 插入和删除元素16. 中序遍历17. 最优二叉树,所有叶子结点的带权路径长度之和为最小18. 先进先出，后进先出19.ABCDEFGHIJ20.后序线索二叉树21. l.length=0;l.listSize=LIST_INIT_SIZE;22.二叉排序树，平衡二叉树三。解答题1.2.3。(1). 1(2). 判断二个有序整数集合是否相同（包括个数，对应值），若相同返回1，不相同返回0(3). O(n)4, (1). i R.t (如果R是指针，则表示为i t)(2). &R.datai.i(3). &R.datai.j(4). &R.datai.v5.(1).(2).将bt1复制到bt2。复制时bt1的左子树复制到bt2的右子树，bt1的右子树复制到bt2的左子树6.(1). FALSE(2).DFSTree(G,p-adjvex)(3).p=p-next