数据结构_期中试卷(含答案).doc

《数据结构_期中试卷(含答案).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、选择题（每小题1分，共10分）1、队列是插入和删除受限的线性表，其删除操作是在线性表的（1）进行。A．表头B．表尾C．任意位置D．指定位置2、下述哪一条是顺序存储结构的优点？（2）。A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 3、设有一个栈，元素的进栈次序为A,B,C,D,E，下列哪个是不可能的出栈序列（3）。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A4、若二叉树的根结点所在的层次为第1层，则该二叉树的第k层上至

2、多有（4）个结点。A.  B．   C．-1   D．+15、设单链表中指针p指向结点m，若要删除m的后继结点（假设该后继结点存在），则需修改指针的操作为（5）。A．p->next=p->next->next;B．p=p->next;C．p=p->next->next;D．p->next=p;6、下面程序段的时间复杂度为（6）。for(inti=0;i

3、表head的尾结点指针p满足（7）。A．p==NULLB．p==headC．p->next==headD．p->next==NULL8、已知二维数组A[0..9,0..9]中，元素a[2][0]的地址为560，每个元素占4个字节，则元素a[1][0]的地址为（8）。A.518B.520C.522D.5249、在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（9）。A．rear％n==frontB．（front+l）％n==rearC．rear％n

4、-1==frontD．(rear+l)％n==front10、假设在一棵二叉树中，度为2的结点数为15，度为1的结点数为10个，则该二叉树的分支总数为（10）个。A.41B.40C.30D.25二、填空题（每空2分，共20分）1.一棵深度为k的完全二叉树（假定根结点所在的层次为第1层），则其结点总数的最小值为（1），最大值为（2）。2．对于一个具有n个结点的单链表（n≥1），在指针变量p指向的结点后插入一个新结点的时间复杂度为（3），在给定值为x的结点后插入一个新结点的时间复杂度为（4）。3.设有一空栈

5、，现有输入序列A，B，C，D，E，经过push,push,pop,push,pop,push,push后，此时的输出序列为（5）。4. 有一个100*90整型数据的稀疏矩阵，非0元素有10个，设每个整型数据占2字节，则用三元组表示该矩阵时，所需的字节数是（6）。5.设栈S和队列Q初始为空。6个元素依a,b,c,d,e,f的顺序通过栈S，一个元素出栈后立即进入队列Q。若这6个元素出队的序列为d,c,b,f,e,a，则栈S的最小容量需（7）。6.若对n阶对称矩阵A[0..n-1,0..n-1]以行序为主序方

6、式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i≤j）的位置k的关系为（8）。7.表达式a+((b*c-d)/e+f*g/h)+x/y对应的后缀表达式是（9）。8.若INDEX（S，T）表示求T在S中的位置的操作，则对于S="Beijing＆Nanjing"，T="jing"，INDEX（S，T）=（10）。三、判断题（每小题2分，共10分，错误打×，正确打√）1．二叉树结构中，任何一个结点都有一个且仅有一个直接前驱和直接后继。.

7、...........()2．在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，对它分别进行中序遍历和后序遍历，则具有相同的结果。.............()3.对线性链表来说，从任意结点开始均能扫描表中全部结点。.............()4.线性表的特点是每个元素都有一个前驱和一个后继。.............()5.栈和队列都是限制存取点的线性结构。.............()四、简答题(本大题有5小题，共40分，每小题分值见各题标注)1．（6分）已知一棵二叉树如下，请分别写出按前序、中

8、序、后序遍历时得到的字符序列。ABCDEFGHIJ2．（6分）设x，n为整型变量，且n>0，下面程序片段中语句x/=2执行次数的数量级是多少？试进行分析。用“O”记号表示。x=n*n;while(x>=1)x/=2;3．（8分）用栈实现将中缀表达式：8*(3+5)+5/3#转换成后缀表达式，画出栈的变化过程图（符号“#”为表达式结束符）。4．（10分）已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这棵二叉