数据结构期末试题1及答案.doc

《数据结构期末试题1及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、试卷A1、顺序表中所有结点的类型必须相同。　　　　　　　　　（　）2、链接表中所有灵活利用存储空间，所以链表都是紧凑结构。(）3、用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　4、Shell排序方法是不稳定的。　　　　　　　　　　（　）5、只允许最下面的二层结点的度数小于2的二叉树是完全二叉树()6、若检索所有结点的概率相等，则内部路径长度大的二叉树其检索效率高。　　　　　　　　　　　　　　　　　　　　　　　　　（　）

2、　　　　　　　　　　　　7、n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。8、广义表中，若限制表中成分的共享和递归所得到的结构是树结构）9、多维数组元素之间的关系是线性的。（　）10、任何无环的有向图，其结点都可以排在一个拓扑序列里。()　11、数据的逻辑结构可形式地用一个二元组B＝(K，R)来表示，其中K是__________，R是_____________。12、广义表(a,(a,b),d,e,((i,j),k))的长度是。13、一个串，除自身之外的所有子串都是该串的。14、树形选择排序总的时间开销为。15

3、、按先根次序法周游树林正好等同于按周游对应的二叉树。16、外部路径长度E定义为从扩充二叉树的到每个的路径长度之和。17、在图结构中，如果一个从Vp到Vq的路径上除Vp和Vq可以相同外，其它结点都不相同，则称此路径为一称为回路。18、栈是一种表。19．带权的又称为网络。20、n×n的三对角矩阵按“行优先顺序”存储其三对角元素，已和a11的存储地址为LOC(a11)，矩阵的每个元素占一个存储单元，则aij(i＝1，j=1，2或1＜i＜n，j＝i－1，i，i＋1或i＝n，j＝n－1，n)的存储地址为LOC(aij)＝。21、对于单链

4、表形式的队列，队空的条件是（　　　）　　A、F＝R＝nil　　B、F＝R　C、F≠nil且R＝nil　D、R－F＝122、下述排序算法中，稳定的是（　　　）　　A、直接选择排序　　B、表插入排序　C、快速排序　　　D、堆排序23、四组含C1～C7的结点序列中，哪一种是下列有向图的拓扑序列（　　　）A、C1，C2，C6，C7，C5，C4，C3　　　B、C1，C2，C6，C3，C4，C5，C7C、C1，C4，C2，C3，C5，C6，C7　D、C5，C7，C4，C1，C2，C6，C324、下列广义表中，长度为2的有（　　　）　　A＝

5、(a，b)　　　　B＝((c，(a，b))，d)　　C＝(c，(a，b))　　D＝((a，b)，(c，(a，b)))　　①A　　　②A，C　　③A，B　　　　④A，B，C，D25、树最适合用来表示()。A、有序数据元素　　　　　　　　B、无序数据元素C、元素之间具有分支层次关系的数据　D、元素之间无联系的数据26、判定一个栈ST(最多元素为m0)为空的条件是()。A、ST->top!=0B、ST->top==0C、ST->top!=m0D、ST->top==m027、在一个单链表中，若删除p所指结点的后续结点，则执行()。A、

6、p->next=p->next-next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p=p->next->next28、递归函数f(n)=f(n-1)+n(n>1)的递归体是()。A、f(1)=0B、f(0)=1C、f(n)=f(n-1)+nD、f(n)=n29、广义表((a,b),c,d)的表尾是()。A、aB、bC、(a,b)D、(c,d)30、在线索化二叉树中，t所指结点没有左子树的充要条件是()。A、t->left==NULLB、t->ltag==1C、

7、t->ltag==1且t->left==NULL　D、以上都不对31、在双链表中，要在指针变量P所指结点之后插入一个新结点，请按顺序写出必要的算法步骤。　(设：P所指结点不是链表的首尾结点，q是与p同类型的指针变量)32、已知待排序文件各记录的排序码顺序如下　　72　　73　　71　　23　　94　　16　　05　　68　请列出快速排序过程中每一趟的排序结果。33、已知一查二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树，并且写出该二叉树的先序序列。34、画出下列网络的最小生成树。5、画出广

8、义表W(X(W，a，Y(W))，Y(W))的双链图表示36、下面给出了起泡排序算法，请填写算法中的空框，使算法正确。　　structnode{　　　　　　　　int　　key;　　　　　　　　datatypeinfo;　　　　　　　}node,*lnode；　　inti，j;