《期末复习题_数据结构》由会员分享，可在线阅读，更多相关《期末复习题_数据结构（16页珍藏版）》请在金锄头文库上搜索。
1、中国石油大学（北京）远程教育学院 期 末 复习题一、选择题（本大题共15小题，每小题2分，共30分）1. 以下与数据的存储结构无关的术语是（ ）A、循环队列 B、链表C、哈希表 D、栈2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）A、110 B、108C、100 D、1203. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ ）A、head= =NULL B、headnext= =NULL C、headnext= =head D、head!=NULL4. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能
2、出现的出栈序列是（ ） A、2，4，3，1，5，6B、3，2，4，1，6，5C、4，3，2，1，5，6D、2，3，5，1，6，45. 下列关键字序列中，构成小根堆的是（ ）A、12，21，49，33，81，56，69，41 B、81，69，56，49，41，33，21，12 C、81，49，69，41，21，56，12，33 D、12，21，49，33，81，41，56，696. 下列数据结构中，不属于二叉树的是（ ）A、B树 B、AVL树 C、二叉排序树 D、哈夫曼树7. 用顺序存储的方法来存储一棵二叉树，存放在一维数组A1.N中，若结点Ai有右孩子，则其右孩子是（ ）。A、A2i B、A2
3、i-1 C、A2i+1 D、Ai/28. 设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ ）A、 5 B、 6 C、7 D、 89. 有数据53，30，37，12，45，24，96，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列输入（ ）A、45，24，53，12，37，96，30B、37，24，12，30，53，45，96C、12，24，30，37，45，53，96D、30，24，12，37，45，96，5310. 对下面有向图给出了四种可能的拓扑序列，其中错误的是（ ）A、1，5，2，6，3，4B、1，5，6，2，
4、3，4C、5，1，6，3，4，2 D、5，1，2，6，4，311. m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( ) A、 m/2+1 B、m/2-1 C、m/2 D、m12. 散列文件也称为( ) A、顺序文件 B 、索引文件C、直接存取文件 D、间接存取文件13. 数据结构是（ ）A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合14. 从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ ）A、线性结构B、树形结构C、线性结构和树型结构 D、线性结构和图状结构15. 设p为指向双向循环链
5、表中某个结点的指针，p所指向的结点的两个链域分别用pllink和prlink表示，则同样表示p指针所指向结点的表达式是（ ）A、pllink B、prlinkC、pllinkllink D、pllinkrlink16. 若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）A、 |top2-top1|=0 B、 top1+1=top2 C、 top1+top2=m D、 top1=top217. 若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（ ）A、10 B、11C、12D、不确定的18
6、. 树的先根序列等同于与该树对应的二叉树的（ ）A、先序序列B、中序序列C、后序序列 D、层序序列19. 下面关于哈希(Hash，杂凑)查找的说法正确的是( )A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的 C、不存在特别好与坏的哈希函数，要视情况而定D、若需在哈希表中删去一个元素，解决冲突都只要简单的将该元素删去即可20. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。 A、 68，11，18，69 23，93，73 B、 68，11，69，23 18，93，73 C、 93，73 68，11，69，23，18 D、 68，11，69，23，
7、18 93，7321. 下列关键字序列中，构成小根堆的是( )A、 (84，46，62，41，28，58，15，37) B、 (84，62，58，46，41，37，28，15)C、 (15，28，46，37，84，41，58，62) D、 (15，28，46，37，84，58，62，41)22. ISAM文件和VASM文件属于( ) A、索引非顺序文件 B、顺序文件C、索引顺序文件 D、散列文件23. 下面程序段的时间复杂度为（ ）for (i=0; im; i+)for (j=0; jnext=s-next；s-next=p； B、s-next=p；q-next=s-next；C、p-nex
8、t=s-next；s-next=q； D、s-next=q；p-next=s-next；25. 为便于判别有向图中是否存在回路，可借助于（ ）A、广度优先搜索算法 B、最小生成树算法 C、最短路径算法 D、拓扑排序算法26. 若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ ）A、SXSSXXXX B、SXXSXSSXC、SXSXXSSX D、SSSXXSXX27. 设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是( )A、2 B、3 C、5 D、628. 假设以数组A
9、m存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位 置为（ ）。A、(rear-length+m+1)%m B、(rear-length+m)%m C、(rear-length+m-1)%m D、(rear-length)%m29. 在一个链队列中，front和rear分别为头指针和尾指针，则插入一个结点s的操作为（ ）。A、s-next=rear;rear=s; B、front=front-next;C、s-next=front;front=s; D、rear-next=s;rear=s;30. 对于哈希函数H(key)=ke
10、y%13,被称为同义词的关键字是（ ）A、35和41 B、 23和39 C、15和44 D、25和5131. 采用二叉链表存储的n个结点的二叉树，共有空指针（ ）个。A、n+1 B、n C、n-1 D、2n-132. 连通网的最小生成树是其所有生成树中（ ）A、顶点集最小的生成树 B、边集最小的生成树C、顶点权值之和最小的生成树 D、边的权值之和最小的生成树33. 对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为（ ）A、123，145，298，314，486，508 B、508，314，123，145，486，298C、486，314
11、，123，145，508，298 D、298，123，508，486，145，31434. 任何一个无向连通图的最小生成树( )。A、一定有多棵 B、可能不存在 C、一棵或多棵 D、只有一棵35. 无向图的邻接矩阵是一个( )A、对角矩阵 B、上三角矩阵 C、对称矩阵 D、零矩阵36. 设无向图G-=(V,E)和G=(V,E),如G为G的生成树，则下列说法中不正确的是( )。A、G为G的无环子图 B、G为G 连通分量C、G为G极小连通子图且V=V D、G为G的子图37. 以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ ）A、 v1，v2，v3，v4，v5，v6，v7 B、 v1，v2，v5，v4，v3，v7，v6C、 v1，v2，v3，v4，v7，v5，v6 D、 v1，v2，v5，v6，v7，v3，v438. 下面几个符号串编码集合中，不是前缀编码的是（ ）A、0,10,110,1111 B、0,1,00,11C、00,010,0110,1000 D、b,c,aa,ac,aba,abb,abc39. 希尔排序的增量序列必须是（ ）。A、 递增的 B、递减的 C、随机的
