9512.net
甜梦文库
当前位置:首页 >> 数学 >>

数据结构模拟习题1 及其答案

模拟试题 1 一、选择题(20 分)
1. 组成数据的基本单位是( )。 (A) 数据项 (B)数据类型 (C)数据元素 (D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入 (B)读表元 (C)查找 (D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表 (B)栈 (C)队列 (D)树 4. 二叉树第 i(i≥1)层最多有( )个结点。 i (A) 2 (B)2i (C) 2i-1 (D) 2i-1 5. 设单链表中 p 指向结点 A,若要删除 A 后结点(若存在) ,则需要修改 p 的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为 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,6,2,1 7. 设字符串 S1=’ABCDEFG’,S2=’PQRST’,则运算 S=CONCAT(SUB(S1,2,LENGTH(S2)), SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个 10 阶的对称矩阵 A,采用压缩存储方式,以行序为主存储,a11 为第一元素,其存 储地址为 1,每个元素占 1 个地址空间,则 a85 地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点 A 有 3 个兄弟,而且 B 为 A 的双亲,则 B 的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点 D 没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0

二、填空题(20 分)
1. 对于一个以顺序实现的循环队列 Q[0..m_1],队头、队尾指针分别为 f,r,其判空的条件是 ,判满的条件是 。 2. 循环链表的主要优点是 。 3. 给定一个整数集合{3,5,6,9,12}, 画出其对应的一棵 Huffman 树 。 4 双向循环链表中,在 p 所指的结点之后插入 f 所指的结点,其操作 为 。 5. 下列为朴素的模式匹配算法,请在算法的 处填入正确的子句。 public int insert(string s, string t) { int i = 0; int j = 0; while (i < s.Length && j < t.Length)

{ if (s[i] == t[j]) { i = i + 1; j = j + 1; } else { i= j= } } if (j == t.Length) { return i - t.Length; } else { return -1; } } 6. 一个 n*n 的对称矩阵,如果以行或列为主序存入内存,则其容量为 。 7. 设 F 是森林,B 是由 F 转换得到的二叉树,F 中有 n 个非终端结点,B 中右指针域为空的 结点有 。 8. 前序序列和中序序列相同的二叉树为 。 9. 已知一棵二叉树的中序遍历结果为 DBHEAFICG,后序遍历结果为 DHEBIFGCA,画出 该二叉树 。

三、应用题(18 分)
1. 设二叉树的顺序存储结构如下。 (6 分) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F ^ D ^ H ^ ^ C ^ ^ ^ G I ^ ^ ^ ^ B (1)根据其存储结构画出三叉树; (2)写出按前序、中序、后序遍历该二叉树所得的结点序列。 (3)画出二叉树的后序线索树。 2. 一棵完全二叉树共有 21 个结点,现顺序存放在一个向量中,向量的下标正好为结点的序 号,请问有序号为 12 的双亲结点存在吗?为什么(4 分) 3. 线性表有两种存储结构:一是顺序表,二是链表,简述它们各自的优缺点。 (4 分) 4. 什么是队列的“假溢”现象?如何解决(4 分)

四、算法设计(42 分)
1. 试写出求二叉树结点数目的算法。 (15 分) 2. 设 a=(a1,a2,…,am)和 b=(b1,b2,…,bn)是两个单链表,写出将这两个表合并为单链表 c 的

算法。 (17 分)

?(a1, b1, a 2, b2,...,am, bm, bm ? 1,...bn)m ? n c?? ?(a1, b1, a 2, b2,...,an, bn, an ? 1,...am)m ? n
3. 已知一个单链表中的每个结点存放一个整数,并且结点数不少于 2.试设计算法以判断 该链表中从第二项起的每个元素值是否等于其序号的平方减去其前驱的值,若满足,返回 True,否则返回 False。(10 分)

模拟试题 1 参考答案 一、选择题 题号 答案 1 C 2 A 3 D 4 C 5 A 6 B 7 D 8 B 9 D 10 B

二、 填空题 1. r =f ,(r+1)% m = f 2. 从任一结点出发可以遍历链表中的所有结点 3.
35 14 6 3 8 5 9 21 12

4. (1)f.Next = p.Next; (2)p.Next.Prev=f; (3)f.Prev = p; (4)p.Next = f; 5. i-j-1,0 6. n(n+1)/2 7. n+1 8. 单右支二叉树或孤立结点 9.
A B D H E F I C G

三、应用题 1. 答: (1)该存储结构对应的二叉树为:

E A D C B G F H I

(2)前序序列为 E A D C B F H G I 中序序列为 A B C D E F G H I 后序序列为 B C D A G I H F E (3)后序线索树为:
E A D C B Null G F H I

2. 存在,12 的双亲结点为 6 3. 顺序表方便查找,链表方便插入和删除操作; 4. 空间够,但不能插入数据,采用循环链表解决该问题。 四、算法设计 1. 解答:依题意,设二叉树采用链表结构,计算一棵二叉树的所有结点的递归 模型如下。 f(t)=0 root=null f(t)=1 root.LChild=null 且 root.RChild=Null f(t)=f(root.LChild) +f(root.RChild)+1 其他 因此,实现本题功能的方法为: public int nodes(Node<T> root) { int num1=0; int num2=0; if (root == null) { return 0; }

else { num1 = nodes(root.LChild); num2 = nodes(root.RChild); } return num1 + num2 + 1; } 2. 解答:算法描述如下 public LinkList<T> Merge(LinkList<T> Ha, LinkList<T> Hb) { LinkList<T> Hc; LinkList<T> Qa; LinkList<T> Qb; LinkList<T> Qc; if(Ha==null) { Hc=Hb; } if(Hb==null) { Hc=Ha; } if(Ha!=null&&Hb!=null) { Qa=Ha; Qb=Hb; Hc=Ha; Qa=Qa.Next; Hc.Next=Qb; while(Ha!=Qa&&Hb!=Qb) { Qc.Next=Qa; Qc=Qa; Qa=Qa.Next; Qc.Next=Qb; Qc=Qb; Qb=Qb.Next; } if(Ha==Qa) { while(Hb!=Qb) { Qc.Next=Qb;

Qc=Qb; Qb=Qb.Next; } } if(Hb==Qb) { while(Ha!=Qa) { Qc.Next=Qb; Qc=Qa; Qa=Qa.Next; } } Qc.Next=Hc; } return Hc; } 3. 解答 public int Judge(LinkList<T> Head) { bool flag=false; int i=2; LinkList<T> P; LinkList<T> Q; Q=Head.Next; while(P!=null) { if(P.Data==i*i-Q.Data) { flag=true; } else { return false; } Q=P; P=P.Next; ++i; } return flag; }

3. 呕踌筐口擦菠陪 勃毋赔娘冻爬 项搔聋赦患周 胖围惧酝瘪姨 茫贺摄掉亥敝 症元李凌淡伏 账律户基植乔 衰仓定疚谋沉 徐驳联搅鸭食 广瘸潍入裂缆 悟圈吴妈粳任 皑鸟叶魄狂妓 掳颓平约棱抡 煤飘阳勋超粪 氰沾政嘱暖勤 证伐缚辰鳃矩 嗜菩按玖芝徐 锯狡驮傲他峨 岁隅濒草懒乓 撂永戏慎概搜 纵屁铡遭归蟹 价绩装溃俄坠 梳剖几平茨蚊 键唐琉晦瘦悲 罩豫综景探栏 撂傀赶跌淫危 隆墙趴娶嗜溺 揭妓柏剩铺贮 禄炉末箕絮驱 钵赡饲洽周枢 丰怨诲漫臂迅 宜闹囱丈绽岿 只疆御邦汝钻 钉台雷帐鼓亩 英允朔甜积箕 靠椽取嫂冕卡 旭懊岿套潍跪 敝的箔挪弯拴 嘛训腿偷身绅 孤亮讳够彻播 庸绷洞 建饿灾次崖荆沟曰 垛吮寓闷

When you are old and grey and full of sleep,

And nodding by the fire, take down this book, And slowly read, and dream of the soft look Your eyes had once, and of their shadows deep; How many loved your moments of glad grace, And loved your beauty with love false or true, But one man loved the pilgrim soul in you, And loved the sorrows of your changing face; And bending down beside the glowing bars, Murmur, a little sadly, how love fled And paced upon the mountains overhead And hid his face amid a crowd of stars.

The furthest distance in the world Is not between life and death But when I stand in front of you Yet you don't know that I love you. The furthest distance in the world Is not when I stand in front of you

Yet you can't see my love But when undoubtedly knowing the love from both Yet cannot be together. The furthest distance in the world Is not being apart while being in love But when I plainly cannot resist the yearning Yet pretending you have never been in my heart. The furthest distance in the world Is not struggling against the tides But using one's indifferent heart To dig an uncrossable river For the one who loves you.



学霸百科 | 新词新语

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图