数据结构期中试题c++(考题)

《数据结构期中试题c++(考题)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、〔据结构（C++版）期中考试试题（2009-2010学年第一学期）一、单项选择题（每空2分，共40分）1.在数据结构屮，从逻辑上可以把数据结构分为（）。A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构2.算法分析的A的是（①），算法分析的两个主要方面是（②）。①A.找出数据结构的合理性B.研宄算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性②A.可读性和文档性B.正确性和简明性C.数据复杂性和程序复杂性D.空间复杂性和时间复杂性3.在下面关于线性表的叙述中，选出正确的一项（）。A.线性

2、表的每一个元素都有一个直接前驱和直接后继B.线性表中至少要有一个元素C.线性表中的元素必须按递增或递减的顺序排列D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继4.如果进栈序列为el、e2、e3、e4,则可能的出栈序列是（）。A.e3，el，e4，e2B.e2,e4，el，e3C.el,e2，e3，e4D.e3，e4，el，e25.设有栈S和队列Q，其初始状态为空，元素el、e2、e3、e4、e5、e6依次入栈，出栈的元素则进入队列Q,若6个元素出列的顺序是e2、e4、e3、e6、e5、el,则栈S的容量至少应是（）oA.6B

3、.4C.3D.26.非空的循环单链表first的尾结点p满足（）。A.p->link==NULLB.p==NULLA.p-〉Iink==firstB.p==first1.在循环双链表的p结点之后插入s结点的操作是（）。A.p->rLink=s;s-〉lLink=p;p-〉rLink->lLink=s;s->rLink=p->rLink;B.p->rLink=s;p->rLink->lLink=s;s-〉lLink=p;s->rLink=p->rLink;C.s->lLink=p;s->rLink=p-〉rLink;p->rLink=s;p-〉rLink->l

4、Link=s;D.s->lLink=p;s-〉rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;2.对一个满二义树，m个树叶，n个结点，深度为11，则（）oA.n=h+mB.h+m=2nC.m=h-lD.n=2h-l3.在下列关于二义树的叙述中，选出正确的一项（）。A.在二叉树中，任何一个结点的度数都是2B.二叉树的度为2C.在二叉树屮至少有一个结点的度是2D.—棵二叉树的度可以小于24.如果一棵二叉树中任一结点的值都大于其左子树中所有结点的值，且小于其右子树中所有结点的值，现欲得到各结点值的递增序列，试问应釆用的遍历的

5、方法是（）。A.先序遍历B.屮序遍历C.后序遍历D.层次遍历11.1如阁所示的4棵二叉树中，（）不是完全二叉树。ABCD12.按照二叉树的定义，具有3个结点的二叉树有（）种。A.3B.4C.5D.613.深度为5的二叉树至多有（）个结点。A.16B.32C.31D.1012.己知广义表LS=（（a，b，c），（d，e，f）），运用head和tail函数取出LS中原子e的运算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））13

6、.稀疏矩阵一般的压缩存储方法主要有（）两种。A.二维数组和三维数组B.三元组和散列表C.三元组和十字链表D.散列表和十字链表14.在N个结点的线索二叉树中，线索的数目为（）。A.N-1B.NC.N+1D.2N15.在一棵完全二叉树中，若编号为i的结点有左子女，则其左子女的编号为（）;若编号为i的结点有右子女，则其右子女的编号为（）;编号为i的结点的双亲结点的编号为（）。A.2iB.2i+lC.2i-lD.L"2」二、填空题（每空1分，共10分）1.单链表表示法的基本思想是用表示结点间的逻辑关系。2.在一个循环队列Q屮，判断队空的条件为，判断队满的条件为O3.

7、中缀表达式A+B*（C-D）-E/F的后缀表示是。4.串是一种特殊的线性表，其特殊性体现在o5.深度为k（设根的层数为1）的完全二叉树至少冇个结点，至多冇个结点。6.线索二叉树的左线索指向其，右线索指向其。7.下阁为某树的双亲表示法存储示意阁：下标dataparent0A-11B02C03D14E2则结点D、E的双亲结点分别为<三、简述下述算法的功能（每小题5分，共20分）1.（1）templatevoidinverse（TA[]，intn）Ttemp;for(inti=0;i<=(n-1)/2;i++)temp=A[i];A[i]=A[n-

8、i-l];A[n-i-l]=temp;}}⑵temp