《数据结构C》模拟试题

《《数据结构C》模拟试题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、山东科技大学继续教莓院题号三四五；弋总'得分评卷策核人得分《数据结构C》模拟题班级学号一、选矍(20分)1.组成数据的基本单位是((A)数据做)数据类酸)数据元素2.线性表的链接实现冊((A)插入3.串的逻辑结构倚(A)线性表(D)数据变量)运算。(B)读表元)的逻辑结构不同(B)栈(C)查癥)定位(C)队列)个结点。(C)2「(D)树4.二叉树第i(41)层最多有((A)2'(B05.设单链表中p指向结点A,若要删餘后结点(若存在)，则需要僅p的操作为()(A)p.Next=p.Next.Next

2、(B)p=p.Next(C)p=p.Next.Next(D)p.Next=p6.设一数列的输入顺序为1,2,3,4,5,6,通过栈操作不可能排成的输岀序列为()(A)3,2,5,6,4,1(B)1,5,4,6,2,3(C)2,4,3,5,1,6(D)4,5,3,6217.设字符串S1二'ABCDEFG',S2=‘PQRST；贝9运算S=CONCAT(SUB(S1,2丄ENGTH(S2)),SUB(S1丄ENGTH(S2),2))的结果为()(A)JBCQRJ(B)4BCDEF(C)'BCDEFG，8

3、.有一个10阶的对總阵采用压缩存储方式，以行序为主存储，每个元素占1个地址空间，则385地址为()(A)13(B)33(C)189•如果结点A有3个兄弟，而且B为A的双亲，则B的度为((A)3(B)4(C)510.线索化二叉树中第点D没有左孩子的必要条件是()(A)D.Lchild=null(C)D.Rchild=null二、填空题(20分)1.对于一个以顺序实靦循环队列(B)D.ltag=1(D)D.ltag=OQ[0..m_1],队头、队掛行别(D)4BCDEFEF1为第一元素，其存储地址为(D

4、)40)(□)1f,「，其判空的条件是1,2?3.4为,判满的条件是循环链表的主要腕是给定_个整数集侍,5,6,9,12},画出其对应的=l»jffman树。双向循坏链表中，在p所指的结点之后插入f审赭—的飞吉乍，其操作O5.下列为朴素的模式匹配算法，请在算法的处填入正确的子句。publicintinsert(strings,stringt){inti=0;intj=0;while(i

5、}if(j==t.Length){returni-t.Length;}else{return・1；}}6.—个nF的对称矩阵，如果以行或列为主序存入内存，则其鑒为7•设F是森林，B是由F转换得到的二叉树，F中有n个非终玄一针域为空的结点有。ODBHEAFICG,后序遍历结果为DHEBIFGCA,画岀该二叉&前序序列和中序序列相同的二叉树为9.己知一棵二叉树的中序遍历结果为树。应用题18分）1.设二叉树的顺序存储结构如下。（123456786分)91011A

6、Fr-Ad「—

7、—ApA-e—pApApA

8、-G--I—Ap-ApAr—A-8——^4121314151617181920（2）写岀按前序、中序、后序遍历该二叉树所得的结点序列。（3）画出二叉树的后序线榭。2.一棵完全二叉树共有21个结点，现顺序存放在一个向量中，向量的下标正好为结点的序号，W号为12的双亲结点存在吗？为什么（4分）3.线性表有两种存储结构：一是顺序表，二是链表，简述它们瞅（4分）4•什么是队列的“假溢,现象？如何解决4分）四、算法设计（42分）试写出求二叉树结点数目的算法。（15分）2.设a=（an宠，…，a^）和b=（bi

9、,b2,…，bj是两个单链表，写岀将这两个表眷为单链表分）c的算法。（17/a,b,a,b，…，a,b,bb)m,C1122mmm+1n—=V」b,b,a、l(a,b,a,2nn#,・・・a)m>1121m3.已知一个单链表中的每个结点存放一个整数，并且结点数步2•试设计算法以判断该链表中廉二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满fflue,否则返囲Ise。(10分）飞选择题题号12345678910答案CADCABDBDB1、填空题1.r=f,(叶1)%m=f2.从任一结点出发可

10、以遍历链表中的所有结点3.351421(68912354.(1)f.Next=p.Next；(2)p.Next.Prev=f；(3)f.Prev=p;(4)P567Next=f;i-j-1.0n(n+1)/2n+1单右支二叉树或孤立结点9.A三、应用题1.答：(1)该存储结构对应的二叉树为::EAHDCB'：(1)前序序列为EADCBFHGI中序序列为ABCDEFGHI后序序列为BCDAGIHFE(1)后序线索树为：F)H八八G・-E(A：D4“CBNull*1.存在