数据结构第三章栈和队列A_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
文档贡献者
评价文档：
喜欢此文档的还喜欢
数据结构第三章栈和队列A
数​据​结​构​课​件
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
大小：743.00KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢大学有机化学推断结构试题（A）及答案解析（可编辑）,有机化学试题及答案,高中有机..
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
大学有机化学推断结构试题（A）及答案解析（可编辑）
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口ABCDE和12345有几种排列组合请附上公式和解决办法，我数学不好，谢谢啦要5个元素的,比如说A1B2C3D4E5,依此类推_百度作业帮
拍照搜题，秒出答案
ABCDE和12345有几种排列组合请附上公式和解决办法，我数学不好，谢谢啦要5个元素的,比如说A1B2C3D4E5,依此类推
ABCDE和12345有几种排列组合请附上公式和解决办法，我数学不好，谢谢啦要5个元素的,比如说A1B2C3D4E5,依此类推
25种,两钟量的个数的乘积
*2*3*4*5*6*7*8*9*10个数的阶乘
题目没问清楚啊。。。。要几个元素组成一个量啊？《数据结构》试卷A (开一页) 站点________专业年级________姓名_________学号_________成绩_________ 一、填空题（每空1分，共22分） 1、数据结构被形式地定义为（D, R），其中D是 的有限集合，R是D上的 有限集合。 2、一个算法的效率可分为 效率和 效率。 3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 _
_______个元素。 4、在一个循环队列中，队首指针指向队首元素的 位置。 5、在具有n个单元的循环队列中，队满时共有 个元素。 6、向栈中压入元素的操作是先 ，后 。 7、 称为空串； 称为空白 串。 8、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的 起始存储位置（基地址）为1000，则数组A的体积（存储量）为 ；末尾元素 A57的第一个字节地址为 ；若按行存储时，元素A14的第一个字节地址为 ；若按列存储时，元素A47的第一个字节地址为 。 9、设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。 10、线性有序表（a1，a2，a3，...，a256）是从小到大排列的，对一个给定的值k，用二 分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 次。设有 100个结点，用二分法查找时，最大比较次数是 。 11、散列法存储的基本思想是由 决定数据的存储地址。 二、判断题（每题1分，共10分） （ ）1. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结 构。 （ ）2.二叉树中所有结点个数是2k-1-1，其中k是树的深度。 （ ）3. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）4.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ ）5.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有 2i－1个结点。 （ ）6. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各 个单元向前移动。 （ ）7.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域 中有n+1个为空指针。 （ ）8. 具有12个结点的完全二叉树有5个度为2的结点。 （ ）9. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （ ）10. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 三、单项选择题（每小题2分，共18分） （ ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称 之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素 的地址是　　　　　（A）110 （B）108 （C）100 （D）120 （ ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： （A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序 （ ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均 要移动 个元素 　　　　　（A）8 （B）63.5 （C）63 （D）7 （ ）5 判定一个队列QU（最多元素为m0）为满队列的条件是 Ａ．QU-&rear － QU-&front = = m0 Ｂ．QU-&rear － QU-&front －1= = m0 Ｃ． QU-&front = = QU-&rear Ｄ．QU-&front = = QU-&rear+1 （ ）6. 链表是一种采用 存储结构存储的线性表； 　　　　　（A）顺序 （B）链式 （C）星式 （D）网状 （ ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以 （ ）8． 线性表Ｌ在 情况下适用于使用链式结构实现。 　　　　（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 　　　　（Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 （ ）9. 若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3， ...，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 四、简答题（10分） 1、已知如图所示的有向图，请给出该图的: （1） 每个顶点的入/出度； （2） 邻接矩阵； （3） 邻接表； （4） 逆邻接表。2、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表 L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点 由数据（占2个字节）和指针（占2个字节）组成，如下所示： 05U17X23V31Y47Z^^100120其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址 为多少？末结点的起始地址为多少？ 五、写出下列程序段的输出结果（栈的元素类型SElem Type为char）。 （1） 　　void main( ){ 　　　Stack S; 　　　char x,y; 　　　InitStack(S); 　　　x='c';y='k'; 　　　push(S,x); push(S,'a'); push(S,y);结果：_____________________ （2）写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){ 　Queue Q; Init Queue (Q); 　Char x='e'; y='c'; 　EnQueue (Q,'h'); EnQueue (Q,'r'); EnQueue (Q,'y'); 　DeQueue (Q,x); EnQueue (Q,x); 　DeQueue (Q,x); EnQueue (Q,'a'); 　while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; 　Printf(x); } 结果：_____________________ 6.假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19， 0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二 进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 五、算法设计（在下列算法的横线内填上适当的语句或表达式。） 1、直接选择排序 void selectsort (int R[ ] ) // 按递增序对R[ 0 ] ~R[n-1] 进行直接选择排序 { int i, j, k, for (i=0; i&= ; i++) { k= for (j= ; j&=n-1; j++) if (R[ j ] R[ k ] ) k=j; if （ ） { temp=R[ i ]; R[ i ] = ; R[ k ]= } } } 2、中序遍历二叉树 设二叉树用二叉链表表示，以t为根指针，二叉链表结点的类型为node；栈s的元素类型 为指向node的指针类型, 栈容量m足够大。中序遍历的非递归算法如下：　 struct node { node *lc,* }; void preorder (node *t) { node *s[m] ，*p= int top =- 1；//置栈空do { while (p!=NULL) { s[++top] = ; ; } if (top!= -１) ｛p=s[top- -]； 　　　　　　　　　　　； 　　　　　　　　　　； 　　}　 } while ((-------) || ( p ! =NULL )); } 　 一、填空题（每空1分，共22分） 1、 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上 的 关系 有限集合。 2、一个算法的效率可分为 时间 效率和 空间 效率。 3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 4、在一个循环队列中，队首指针指向队首元素的 前一个 位置。 5、在具有n个单元的循环队列中，队满时共有 n-1 个元素。 6、向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 7、 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格 符）组成的串 称为空白串。 8、假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的 起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素 A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)×6+ ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4) ×6＋1000）＝1276 。 9、设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 10、线性有序表（a1，a2，a3，...，a256)是从小到大排列的，对一个给定的值k，用二 分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有 100个结点，用二分法查找时，最大比较次数是 7 。 11、散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 一、 判断题（每题1分，共10分） （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型 结构。 （ × ）1.二叉树中所有结点个数是2k-1-1，其中k是树的深度。（应2i-1） （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ × ）2.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 （ × ）3.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有 2i-1个结点。（应2i-1） （ × ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （ √ ）4.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区 域中有n+1个为空指针。 （ √ ）5.具有12个结点的完全二叉树有5个度为2的结点。 （ × ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相 邻。 （ × ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 三、单项选择题（每小题2分，共18分） （ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称 之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ B ）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的 地址是 　　　　　（A）110 （B）108 （C）100 （D）120 （ A （D） （E） （F） （G） ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） 在第i个结点后插入一个新结点（1≤i≤n） 删除第i个结点（1≤i≤n） 将n个结点从小到大排序（ B ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均 要移动 个元素 　　　　　（A）8 （B）63.5 （C）63 （D）7 （ A ）4.判定一个队列QU（最多元素为m0）为满队列的条件是_______ Ａ．QU-&rear － QU-&front = = m0 Ｂ．QU-&rear － QU-&front －1= = m0 Ｃ．QU-&front = = QU-&rear Ｄ．QU-&front = = QU-&rear+1 （ B ）6. 链表是一种采用 存储结构存储的线性表； 　　　　　（A）顺序 （B）链式 （C）星式 （D）网状 （ D ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （A）必须是连续的 （B）部分地址必须是连续的 （C）一定是不连续的 （D）连续或不连续都可以（ B ）8． 线性表Ｌ在 情况下适用于使用链式结构实现。 　　　　（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 　　　　（Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 （ C ）9. 若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，. ..，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 四、1、 略 2、 答：X= 116 Y= 五、 1、 答：输出为&stack&。 2、 答：输出为&char&。0Z=100首址=108末址=112六、解：方案1；哈夫曼编码 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ......19, 21, 32 　　　　　　　（100） 　　　　（40） （60） 19 21 32 （28） （17） （11） 　　　　　　　　 7 10 6 （5） 　　　　　　　　 2 3 方案比较：方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2. 61 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码 六、阅读分析题（10分） 指出以下算法中的错误和低效（即费时）之处，并将它改写为一个既正确又高效的算法。答：错误有两处： ① 参数不合法的判别条件不完整。例如表长为10，若从第一位置（i=1）删除10个元素 （k=10）,要求合理但会被判为非法。 合法的入口参数条件为（0&i≤a.length）^ (0≤k≤a.length-i) 应将if ( i&1 || k&0 || i+k& a.length ) return INFEASIBLE 改为：if (！（（0&i≤a.length）^ (o≤k≤a.length-i)）) return INFEASIBLE 　第二个FOR语句中，元素前移的次序错误。应将for ( j = a. j&=i+1; j--) a.elem[j-1] = a.elem[j]; 　改为for (j&=i+1; j = a. j++) a.elem[j-1] = a.elem[j];《数据结构》试卷B (开一页) 站点________专业年级________姓名_________学号_________成绩_________ 一、 填空题（每空1分，共15分） 1. 向量、栈和队列都是 结构，可以在向量的 位置插入和删除元素；对 于栈只能在 插入和删除元素；对于队列只能在 插入和 删除元 素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 。不允许插入和 删除运算的一端称为 。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它 们之间的 和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素 个数与 有关。 5. 在具有n个单元的循环队列中，队满时共有 个元素。 6. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两 次查找成功的结点数为 ；比较四次查找成功的结点数为 ；平均查找长度为 。 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂 类型。（）2. 在表结构中最常用的是线性表，栈和队列不太常用。（ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进 先出型结构。 （ 表。 （ （ （ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性 ）5.线性表的逻辑顺序与存储顺序总是一致的 ）6. 栈和队列是一种非线性数据结构。 ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。（ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把 两个栈的栈底分别设在这片内存空间的两端。 （ ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型 结构。 （ ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。三、单项选择题（每小题1分，共20分） （ ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称 之为：（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ ）2. 若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3， ...，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 （ ）3. 判定一个栈ST（最多元素为m0）为空的条件是 Ａ．ST-&top&&0 Ｂ．ST-&top=0 Ｃ．ST-&top&&m0 Ｄ．ST-&top=m0 （ ）4设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行 序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数 组B中下标k的值是： 　　　　Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1) /2+j （ ）5．具有n(n&0)个结点的完全二叉树的深度为 。 　　　　　　(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 (Ｄ) ?log2(n) +1? （ ）6. 有8个结点的无向连通图最少有 条边。 A．5 B. 6 C. 7 D. 8 7. 数据结构反映了数据元素之间的结构关系。链表是一种 A ，它对于数据元素的 插入和删除 B 。通常查找线性表数据元素的方法有 C 和 D 两种方法，其 中 C 是一种只适合于顺序存储结构但 E 的方法；而 D 是一种对顺序和链 式存储结构均适用的方法。 供选择的答案： A：①顺序存储线性表 ②非顺序存储非线性表 ③顺序存储非线性表 ④非顺序 存储线性表B： ① 不需要移动结点，不需改变结点指针 ②不需要移动结点，只需改变 结点指针 　　③只需移动结点，不需改变结点指针 ④既需移动结点，又需改变结点指针 C：① 顺序查找 ②循环查找 ③条件查找 ④二分法查找 D：① 顺序查找 ②随机查找 ③二分法查找 ④分块查找 E：① 效率较低的线性查找 ②效率较低的非线性查找 ③效率较高的非线性查找 ④效率 较高的线性查找 答案：A＝ B＝ C＝ D＝ E＝ 8. 散列法存储的基本思想是根据 A 来决定 B ，碰撞（冲突）指的是 C ，处 理碰撞的两类主要方法是 D 。 供选择的答案 A，B： ①存储地址 ② 元素的符号 ③ 元素个数 ④ 关键码值 ⑤ 非码属性 ⑥ 平均检索长度 ⑦ 负载因子 ⑧ 散列表空间 C: ①两个元素具有相同序号 ② 两个元素的关键码值不同，而非码属 性相同 　　 ③ 不同关键码值对应到相同的存储地址 ④ 负载因子过大 ⑤ 数据元素过多 D： ① 线性探查法和双散列函数法 ② 建溢出区法和不建溢出区法 ③ 除余法和折叠法 ④ 拉链法和开地址法 答案：A＝ B＝ C＝ D＝ 9. 考虑具有如下性质的二叉树：除叶子结点外，每个结点的值都大于其左子树上的一切 结点的值。并小于等于其右子树上的一切结点的值。 　　现把9个数1，2，3，...，8，9填入下图所示的二叉树的9个结点中，并使之具有上述 性质。此时，n1的值是 A ，n2的值是 B ，n9的值是 C 。现欲把放入此树并使 该树保持前述性质，增加的一个结点可以放在 D 或 E 。 供选择的答案 A～C： ① 1 ② 2 ③ 3 ④ 4 ⑤ 5 ⑥ 6 ⑦ 7 ⑧ 8 ⑨ 9 D～E： ① n7下面 ② n8下面 ③ n9下面 ④ n6下面 ⑤ n1与n2之间 ⑥ n2与n4之间 　　　　⑦ n6与n9之间 ⑧ n3与n6之间 答案：A＝ B＝ C＝ 　　　D＝ E＝ 四、简答题（每小题5分，共25分） 1. 说明线性表、栈与队的异同点。 2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列3. 假设正读和反读都相同的字符序列为&回文&，例如，'abba'和'abcba'是回文， 'abcde' 和'ababab'则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈 和队列等方式正确输出其回文的可能性？ 4. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 5. 给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想 方法。 五、阅读理解（每小题5分，共20分） 1、已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，请写出在 P结点后插入S结点的核心语句序列。 　　　　　　　　　　　　　　 2、阅读下列算法，若有错，改正之。 1. 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){ Queue Q; Init Queue (Q); Char x='e'; y='c'; EnQueue (Q,'h'); EnQueue (Q,'r'); EnQueue (Q,'y'); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,'a'); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); } 2. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){ Stack S; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); 　} } 六、算法设计（每小题5分，共15分。至少要写出思路） 1. 写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。 2. 编写程序，将若干整数从键盘输入，以单链表形式存储起来，然后计算单链表中结点 的个数（其中指针P指向该链表的第一个结点）。 3. 试写一个算法，判别读入的一个以'@'为结束符的字符序列是否是&回文&。一、填空题（每空1分，共15分） 1.向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素； 对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和 删除运算的一端称为 栈底 。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们 之间的 关系 和运算等的学科。 4. 在顺序表中插入或删除一个元素，需要平均移动 表中一半元素，具体移动的元素个数 与 表长和该元素在表中的位置 有关。 5. 在具有n个单元的循环队列中，队满时共有 n-1 个元素。 8. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两 次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O（log2n）&5次（25）。但具体是多少次，则不应当按照公式 来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下 推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！ ！ 二、判断正误（判断下列概念的正确性，并作出简要的说明。）（每小题1分，共10分） （ × ）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复 杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。 （ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后 进先出型结构。 （ √ ）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线 性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （ × ） 5.线性表的逻辑顺序与存储顺序总是一致的 （ × ）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （ √ ）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ √ ）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应 把两个栈的栈底分别设在这片内存空间的两端。 （ × ）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型 结构。 错，后半句不对。 （ × ）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。三、单项选择题（每小题1分，共20分） （ C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称 之为： （A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 （ C ）2.若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，... ，pn，若p1=n，则pi为 Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定 解释：当p1=n，即n是最先出栈的，根据栈的原理，n必定是最后入栈的（事实上题目已经 表明了），那么输入顺序必定是1，2，3，...，n，则出栈的序列是n，...，3，2，1。 （若不要求顺序出栈，则输出序列不确定） （ B ）3、判定一个栈ST（最多元素为m0）为空的条件是 Ａ．ST-&top&&0 Ｂ．ST-&top=0 ST-&top=m0 Ｃ．ST-&top&&m0 Ｄ．( B )4、 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示） 按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一 维数组B中下标k的值是： Ａ．i(i-1)/2+j-1 Ｂ．i(i-1)/2+j Ｃ．i(i+1)/2+j-1 Ｄ．i(i+1)/2+j （ C ）5．具有n(n&0)个结点的完全二叉树的深度为 。 　　　　　(Ａ) ?log2(n)? (Ｂ) ? log2(n)? (Ｃ) ? log2(n) ?+1 log2(n)+1? （ ）6. 有8个结点的无向连通图最少有 A．5 B. 6 7、 答案：A＝ ④ B＝ ② C＝ ③ 8、 答案：A＝ ④ B＝ ① 9、答案：A＝ ⑦ B＝ ④ C＝ C 条边。 C. 7 ④ C＝ ⑥ ③ D＝ ② D. D＝ ① D＝ (Ｄ) ?8 E＝ ④ E＝ ⑥四、简答题（每小题4分，共20分） 1.说明线性表、栈与队的异同点。 刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈 和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。 不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运 算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而 是先进先出表FIFO。 ② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他 运算等等。 2. 试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A3.假设正读和反读都相同的字符序列为&回文&，例如，'abba'和'abcba'是回文，'abcde' 和'ababab'则不是回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等 方式正确输出其回文的可能性？ 答：线性表是随机存储，可以实现，靠循环变量（j--）从表尾开始打印输出； 　　堆栈是后进先出，也可以实现，靠正序入栈、逆序出栈即可； 　　队列是先进先出，不易实现。 　　哪种方式最好，要具体情况具体分析。若正文在机内已是顺序存储，则直接用线性表 从后往前读取即可，或将堆栈栈顶开到数组末尾，然后直接用POP动作实现。（但堆栈是 先减后压还是......） 　　若正文是单链表形式存储，则等同于队列，需开辅助空间，可以从链首开始入栈，全 部压入后再依次输出。 　　 　　 4.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中 可用存储单元的地址必须是连续的。 优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。 ②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放 结点值，另一部分存放表示结点间关系的指针 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（&1），存储空间利用率 低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表； 若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 5.给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G， I，F， 试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想 方法。 解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元 素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将 他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 D 　　 C 　　　　E 　　B H A F G I五、阅读理解（每小题5分，共20分。至少要写出思路） 答：此题答案不唯一，但若从已给定序列中挑选，则限制颇多。 (7) Q=P; (11) P=L; (8) while(P-&next!=Q)P=P-& (10) P=Q; (4) S-&next=P-& P-&next=S; 　　　　　　　　　　　　　　 　　　　　　　　　　　　　　 2、答：这是找结点后继的程序。 共有3处错误。 注：当rtag＝1时说明内装后继指针，可直接返回，第一句无错。 当rtag＝0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再 根再右，所以应当找左子树直到叶子处。r=r-& 直到LTag=1； 应改为：while(!r-&Ltag)r=r-&L 3. 写出下列程序段的输出结果（队列中的元素类型QElem Type为char）。 void main( ){ Queue Q; Init Queue (Q); Char x='e'; y='c'; EnQueue (Q,'h'); EnQueue (Q,'r'); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,'a'); while(!QueueEmpty(Q)){ DeQueue (Q,y);printf(y); }; Printf(x); } 答：输出为&char&。 4. 简述以下算法的功能（栈和队列的元素类型均为int）。 void algo3(Queue &Q){ Stack S; InitStack(S); while(!QueueEmpty(Q)){ DeQueue (Q,d); Push(S,d); }; while(!StackEmpty(S)){ Pop(S,d); EnQueue (Q,d); 　} } 答：该算法的功能是：利用堆栈做辅助，将队列中的数据元素进行逆置。六、算法设计（每小题5分，共15分。至少要写出思路） 1、输入：长度为n的线性表数组A(1:n) 输出：逆转后的长度为n的线性表数组A(1:n)。 C语言描述如下（其中ET为数据元素的类型）：2. 假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个 标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是&空&还是&满&。试编 写相应的入队和出队的算法。 解：这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他 两种见简答题）； 思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则 令tag=1； 若从front一端加到与rear指针相同时，则令tag=0，表示出队已空。 3.试写一个算法判别读入的一个以'@'为结束符的字符序列是否是&回文&。 答：编程如下： int Palindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0 { InitStack(S);InitQueue(Q); while((c=getchar())!='@') { Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b) return ERROR; } return OK; }//Palindrome_Test
《数据结构》试卷A (开一页)——为大家提供各种日常写作指导，同时提供范文参考。主要栏目有：范文大全、个人简历、教案下载、课件中心、 优秀作文、考试辅导、试题库、诗词鉴赏。
相关文档：
下载文档：
搜索更多：
All rights reserved Powered by
copyright &copyright 。甜梦文库内容来自网络，如有侵犯请联系客服。|