《数据结构》期末复习题

《《数据结构》期末复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、中国石油大学（北京）远程教育学院期末复习题一、选择题（本大题共15小题，每小题2分，共30分）1.以下与数据的存储结构无关的术语是（）A、循环队列B、链表C、哈希表D、栈2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A、110B、108C、100D、1203.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）A、head==NULLB、head–>next==NULLC、head–>next==headD、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，69}6.下列数据结构中，不属于二叉树的是（）A、B树B、AVL树C、二叉排序树D、哈夫曼树7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..

3、N]中，若结点A[i]有右孩子，则其右孩子是（）。A、A[2i]B、A[2i-1]C、A[2i+1]D、A[i/2]8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（）16A、5B、6C、7D、81.有数据{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，

4、96，532.对下面有向图给出了四种可能的拓扑序列，其中错误的是（）A、1，5，2，6，3，4B、1，5，6，2，3，4C、5，1，6，3，4，2D、5，1，2，6，4，33.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于()A、[m/2]+1B、[m/2]-1C、[m/2]D、m4.散列文件也称为()A、顺序文件B、索引文件C、直接存取文件D、间接存取文件5.数据结构是（）A、一种数据类型B、数据的存储结构C、一组性质相同的数据元素的集合D、相互之间存在一种或多种特定关系的数据元素的集合6.从逻辑关系来看，数据元素的直接

5、前驱为0个或1个的数据结构只能是（）A、线性结构B、树形结构C、线性结构和树型结构D、线性结构和图状结构7.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示p指针所指向结点的表达式是（）A、p→llinkB、p→rlinkC、p→llink→llinkD、p→llink→rlink8.若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i16=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）A、

6、top[2]-top[1]

7、

8、=0B、top[1]+1=top[2]C、top[1]+top[2]=mD、top[1]=top[2]1.若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（）A、10B、11C、12D、不确定的2.树的先根序列等同于与该树对应的二叉树的（）A、先序序列B、中序序列C、后序序列D、层序序列3.下面关于哈希(Hash，杂凑)查找的说法正确的是()A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定D、若需在哈希表中删去一个元素，解决冲突都只要简单的将该

9、元素删去即可4.下列序列中，（）是执行第一趟快速排序后所得的序列。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，18][93，73]5.下列关键字序列中，构成小根堆的是()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)6.ISAM文件和VASM

10、文件属于()A、索引非顺序文件B、顺序文件C、索引顺序文件D、散列文件7.下面程序段的时间复杂度为（）for(i=0;i