数据结构课后习题.pdf

《数据结构课后习题.pdf》由会员分享，可在线阅读，更多相关《数据结构课后习题.pdf（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、习题一一、单选题1.下列四种基本逻辑结构中，数 据 元 素 之 间 关 系 最 弱 的 是，列队属于A.集合 B.线性结构 C.树形结构 D.图形结构2.线性结构各数据元素之间存在着 的关系，图形结构数据元素之间存在_的关系。A.无关 B,一 对 一,C.一 对 多 D.多对多3.在数据结构中，从 逻 辑 上 看 可 以 把 数 据 结 构 分 为。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构4.算 法 中 的 基 本 操 作 重 复 执 行 的 频 度 称 为 算 法 的;除了考虑存储数据结构本身所占用的空间外，实现算法所用辅助空间的多少称

2、为算法的 OA.时间复杂度 B.空间复杂度 C.硬 件 复 杂 度D软件复杂度5.算 法 分 析 的 目 的 是 ，算法分析的两个主要方面是 o A.找出数据结构的合理性C.分析算法的效率以求改进 A.空间复杂度和时间复杂度C.可读性和文档性6.计 算 机 算 法 指 的 是，它必具备输入、A.计算方法C.解决问题的有限运算序列 A.可行性、可移植性和可扩充性C.确定性、有穷性和稳定性B.研究算法中的输入和输出关系D.分析算法的易懂性和文档性B.正确性D.数据复杂性和程序复杂性输 出 和 等五个特性。B.排序方法D.调度方法B.可行性、确定性和有穷性D.易读性、稳定性和安全性线性表的逻辑顺序与

3、存储顺序总是一致的，这种说法A.正确B.不正确8.线性表若采用链式存储结构时,要求内存中可用存储单元的地址A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以二、填 空 题（将正确的答案填在相应的空中）1.数据逻辑结构包括集合、和 四种类型，树形结构和图形结构统称为 o2 .线性结构中，第一个结点 前驱结点，其余每个结点有且仅有个直接前驱结点；最后一个结点 后继结点，其余每个结点有且仅有 个直接后继结点。3.在树形结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后继结点可以 o4 .在图形结构中，每 个 结 点 的 前

4、 驱 结 点 数 和 后 继 结 点 数 可 以。5 .线性结构中元素之间存在 关系，树形结构中元素直接存在 关系，图形结构中元素之间存在 关系。6 .算 法 的 五 个 重 要 特 性 是、7 .下列程序段的时间复杂度是f o r(i=0;i n;i+)f o r(j=0;j m;j+)a i 皿=0;8 .下列程序段的时间复杂度是i=s=0;w h i l e(s n)(i+；S+=I；)9 .下列程序段的时间复杂度是s=0;f o r(i=0;i n;i+)f o r(j=0;j n;j+)s+=b i j j j;s u m=s;1 0.下列程序段的时间复杂度是i=l；while（in

5、）i=i*3;习题二一、填空题1.在一个长度为n的向量的第i个元素（l=i=n）之前插入一个元素时，需向后移动 个元素。2.在一个长度为n的向量中删除第i个元素（l=i n e x t=和 p-next 的操作。7.非空的循环单链表head的尾结点（由p所指向）满足条件。二、单选题1.不带头结点的单链表head为空的判断条件是 oA.head=NULL B.head-next=NULLC.head-next=head D.head!=NULL2.带头结点的单链表head为 空 的 判 断 条 件 是-A.head=NULLB.head-next=NULLC.head-next=head D.h

6、ead!=NULL3.非空的循环单链表head的尾结点（由p所指向）满足 oA.p-next=NULL B.p=NULLC.p-next=head D.p=head4.在循环双链表的p所指结点之后插入s所 指 结 点 的 操 作 是。A.p-prior=p;p-next-prior=s;s-next=p-next;B.p-next-prior=s;s-prior=p;s-next=p-next;C.s-prior=p;s-next=p-next;p-next-prior=s;D.s-prior=p;s-next=p-next;p-next-prior=s;p-next=p-next;p-nex

7、t=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;6.一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 OA.s-next=p;p-next=s;B.s-next=p-next;p-next=;C.s-next=p-next;p=s;D.p-next=s;s-next=p;7.在一个单链表中，若删除p所指结点的后继结点，则执行 oA.p-next=p-next-next B.p=p-next;p-next=p-next-nextC.p-next=p-next D.p=p-next-ne

8、xt三、算法描述题1.已知一个向量中的元素按元素值非递减有序排列，编写一个函数删除向量中多余的值相同的元素。2.编写一个函数将一个向量A（有 个元素，且任何元素均不为0）分拆成两个向量，使A中大于0的元素存放在B中，小于0的元素存放在C中。3.已知在一维数组Al,m+n中依次存放着两个向量（a的,.,am）和（也,b2,，ba）,编写一个函数将两个向量的位置互换，即把（b”b2,ba）放 到（ai,a2,.，am）的前面。4.有一个单链表（不同结点的数据值域可能相同），其头指针为h ead,编写一个函数计算数据域为x 的结点个数。5.编写一个函数将不带头结点的单链表L a复制成单链表Lbo6.

9、有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中多余的元素值相同的结点。习题三一、填空题1.栈是限定仅在表尾进行 操作的线性表，表头端称为，表尾端称为，栈的操作特性是 02.队列是限定仅在表尾进行 和在表头端进行 的线性表，列队的操作特性是 O3.以下定义了一个顺序栈：#define MAXSTACK 500typedef struct char dataMAXSTACKl;int top;Jsqstack;sqstack ss;栈空的条件是：,栈满的条件是：;栈顶元素的表达式是:,栈底元素的表达式是:。二、简答题1.设 将 整 数 1,2,3,4依次进栈，但只要出栈时

10、栈非空，则可将出栈操作按任何次序插入在入栈操作之间，请回答下述问题：(1)若入出栈次序为 Push(l),Pop(),Push(2),Push(3),Pop(),Pop(),Push(4),P o p O,则 出 栈 的 数 字 序 列 是 什 么(这 里P u s h (i)表 示 进 栈，P o p ()表 示 出 栈)？(2)能 否 得 到 出 栈 序 列1 4 2 3和1 4 3 2?并 说 明 为 什 么 不 能 得 到 或 者 如 何 得 到。(3)请 分 析1,2,3,4的2 4种 排 列 中，哪 些 序 列 可 以 通 过 相 应 的 入、出栈操作得 到。2.循 环 队 列 的

11、 优 点 是 什 么？如 何 判 别 它 的 空 和 满？三、算法设计题1 .回 文 是 指 正 读 反 读 均 相 同 的 字 符 序 列,如“a b b a 和“a b d b a”均 是 回 文，但“go o d”不 是 回 文。试 写 一 个 算 法 判 定 给 定 的 字 符 向 量 是 否 为 回 文。(提 示：将一半字 符 入 栈。)2.括 号 配 对 检 查，输 入 一 个 只 有 左 括 号“(”和 右 括 号“)”的 序 列，程序对括 号 配 对 的 正 确 性 进 行 检 查 并 给 出 结 果。提 示：配 对 检 查 算 法 中 用 到 栈 结 构。例如 括 号 序 列

12、“()()”、“()()()”为 正 确 配 对，括 号 序 列“()()”、“)()(”为不 正 确 配 对 等。注 意：输 入 序 列 中 只 能 出 现 左 括 号“(”和 右 括 号“)”，序列的语 法 正 确 性 由 用 户 保 证。请 给 出 完 整 的C程 序 描 述。习题四一、填空题1 .已知二维 数 组A m n 采 用 行 序 为 主 方 式 存 储，每 个 元 素 占k个存储单 元，并 且 第 一 个 元 素 的 存 储 地 址 是L o c(A 0 0 ),则A i J j 的 地 址 是2 .二维 数 组A 1 0 2 0 采 用 列 序 为 主 方 式 存 储，每个

13、元素占一个存储单元，并 且A 0 0 的 存 储 地 址 是2 0 0,则A 的 地 址 是 o二、单选题1 .常对数组进行的两种基本操作是 OA.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引2.数组A 中，每个元素的长度为3 个字节，行下标i 从 1到 8,列下标j 从 1到 1 0,存放该数组至少需要的单元数是 oA.80 B.100 C.240 D.2703.数组A 中，每个元素的长度为3 个字节，行下标i 从 1到 8,列下标j 从 1到 10,从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为 oA.SA+141 B.SA+144 C.SA+2

14、22 D.SA+2254.稀疏矩阵一般的压缩存储方法有两种，即 oA.二维数组和三维数组 B.三元组表和散列C.三元组表和十字链表 D.散列和十字链表三、算法描述题假设稀疏矩阵Am*n和 Bm*n都采用三元组表，编写一个函数计算C=A+B,要求C 也采用三元组表表示。习题五一、简答题1.设 s=I AM A STUDENT”，t=GOOD”，q=WORKER”。求：STRLEN(s),STRLEN(t),SUBSTR(s,8,7,),SUBSTR(t,2,1),INDEX(s,A),INDEX(s,t),REPLACES,“STUDENT”，q)o2.已知下列字串：a=THIS，f=ASMPL

15、E，c=GOOD，d=NE”,b=，g=“IS”s=CONCAT(a,CONCAT(CONCAT(b,SUBSTR(a,3,2),SUBSTR(f,2,6)t=REPLACE(f,SUBSTR(f,3,5),c)u=CONCAT(SUBSTR(c,3,1),d)v=CONCAT(s,CONCAT(b,CONCAT(t,CONCAT(b,u)问 s,t,v,STRLEN(s),INDEX(v,g),INDEX(u,g)各是什么?3、简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串。4、两个字符串相等的充要条件是什么？5、设已知两个串为：Si=be cad cabcadf”；82=

16、abc。试求两个串长度，并判读断S2串是否是与的子串。如果S2是否是S1的子串，指出S2在$中的起始位置。二、算法设计题编写算法，在顺序串上实现串的判等操作EQUAL(S,T)o设两个串分别为S=Beijing，T=China”,调用函数 EQUAL(S,T)判断后,如果 S=T,则返回1,否则返回0.习题六一、判断题1、二叉树是树的特殊情形。（）2、二叉树的先序遍历序列中，任意节点均处在其孩子结点之前。（）3、二叉链表是一种逻辑结构。（）4、由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。（）5、n个结点的完全二叉树不唯一。（）6、树的后续遍历序列与其对应的二叉树的后序遍历序列相同。（）

17、7、完全二叉树的某结点若无左孩子，则它必是叶子结点。（）二、选择题1、将一棵树t转换为孩子兄弟链表表示的二叉树h,则t的后序遍历是卜的（）A.先 序 遍 历B.中 序 遍 历C.后序遍历 D.层次遍历2、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。A.先序 B.中序 C.后序 D.从根开始的层次遍历3、已知一棵完全二叉树中共有7 6 8个结点，则该树中共有（）个叶子结点。A.3 8 3 B.3 8 4 C.3 8 5 D.3 8 64、先序遍历和中序遍历相同的二叉树为（）A.只有根

18、结点的二叉树 B.根结点无左孩子的二叉树C.一般二叉树 D,只有根结点的二叉树和所有结点只有右子树的二叉树三、简答题1、一棵树的边集为（a,b）,（b,e）,（a,c）,（c,g）,（a,d）,（d,i）,（c,f）,（c,h）,（d,j）,（i,k）,请画出此棵树的形态，并回答下列问题：（1）树的根是哪个结点？哪些是叶子结点？哪些是分支结点？（2）各结点的度分别是多少？树的度是多少？（3）各结点的层次分别是多少？树的深度是多少？以d为根的子树深度是多少？（4）结点i的双亲是哪个结点？祖先是哪个结点？孩子是哪些结点？兄弟是哪些结点？2、树和二叉树有哪些区别？3、已知二叉树的后序和中序序列如下，

19、构造出该二叉树，写出它的前序遍历序列。后序序歹U：ABCDEFG 中序序歹U：ACBGDFE4、假设用于通信的电文由字符集 岫,斓 胴 中的字母构成，它们在电文中出现的频度分别为 0.31,0.16,0.10,0.08,0.11,0.20,0.04）（1）为这7个字母设计哈弗曼编码。（2）对 这7个字母进行等长编码，至少需要几位二进制数？哈弗曼编码与等长编码相比，能使电文总长压缩多少？四计算题1、设计算法求二叉树的高度。2、按要求写出算法，功能为判断一棵二叉树（采用二叉链表存储结构）是否为完全二叉树。习题七-、单项选择题1、一个有n个顶点的无向图最多有 条边。A.n B n（n-l）C、n（n

20、-l）/2 D、2n2、一个有4个顶点的无向完全图有 条边。A、6 B、12 C、16 D、203、一个有5个顶点的连通图至少有 条边A、3B、4C、5D、6的邻接矩阵是对矩阵。A、有向图B、无向图C、A O V网5、邻 接 表 时 图 的 一 种。A、顺序存储结构 B、链接存储结构C、索引存储结构D、散列存储结构6、采用邻接表存储的图的深度优先遍历算法类似于二叉树的 oA、前序遍历 B、中序遍历 C、后序遍历 D、按层遍历7、采用邻接表存储的图的广度优先遍历算法类似于二叉树的。A、前序遍历 B、中序遍历 C、后序遍历 D、按层遍历8、任何一个无向连通图 最小生成树。A、只有一棵 B、有一棵或

21、多棵C、一定有多棵 D、可能不存在9、一个图的 表示法师唯一的，而 表示是不是唯一的。A、三元组 B、邻接矩阵 C、邻接表 D索引二、简答题1、对图7.23所示有向图，回答下列问题(1)该图是强连通图吗?若不是，则给出其强连通分量。(2)请给出从顶点1到顶点3的所有的简单路径。(3)请给出顶点1的度、入度和出度。(4)请给出其邻接矩阵，邻接表及逆邻接表。2、对图7.24所示无向图，分别给出它从顶点1出发进行深度和广度遍历得到的顶点序列图 7.23有向图3、对图7.25所示无向图，分别画出按普里姆算法和克鲁斯卡尔得到最小生成树的过程。4、对图7.26所示有向图，利用辿杰斯特拉算法，求从顶点1到其

22、余各项点的最短路径5、对图7.27所示有向图,求拓扑序列。习题八一、单选题1、对线性表进行二分查找时，要求线性表必须 oA、以顺序方式存储 B、以链接方式存储C、以顺序方式存储且结点按关键字有序排列D、以链接方式存储且结点按关键字有序排列2、采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 OA、n B、n/2 C、(n+l)/2 D、(n-l)/23、采用二分查找长度为n 的线性时，每个元素的平均查找长度为 oA O(n2)B、O(nlong2n)C、O(n)D、O(long2n)4、有一个序列表为(5,7,8,22,32,40,45,62,70,77,82,97,100),

23、当二分查找值为82的结点时-，次比较后查找成功。A、1 B、3 C、4 D、85、从一个具有n 个结点的单链接表中查找其值等于x 结点时，查找成功的情况下，需平均比较 个结点。A、n B、n/2 C、(n-l)/2 D、(n+l)/2二、填空题1、假设有序线性表A l,，A20上进行二分查找，则比较一次查找成功的结点数为，则比较二次查 找 成 功 的 结 点 数 为,则比较三次查找成功 的 结 点 数 为，则 比 较 四 次 查 找 成 功 的 结 点 数 为,则比较五次查找 成 功 的 结 点 数 为，平均查找长度为 o2、在散列存储中，装填因子a 的值越大，存取数据元素是发生冲突的可能性;

24、a 的值越小，则发生冲突的可能性 o三.简答题、设有一组关键字(19,01,23,14,55,20,84,27,68,11,10,7 7)采用哈希函数H(key)=key%131,、采用开放地址的线性探测再散列方法解决冲突，试 在 01 2 的散列地址空间中对该关键字序列构造哈希表2、对上题中的关键字序列，采用链地址法，画出相应的哈希表3、对有序表(5,8,27,35,45,48,57,72,89,9 5),采用二分查找，画出二分查找过程的二叉判定树，并计算其平均查找长度。四.算法设计题1 .将折半查找算法改写为递归的形式。2.以线性探测再散列为例，给出散列表的查找算法。习题九一、单选题1、在

25、所有排序方法中、关键字比较的次数与记录的初始排列次序无关的是 OA、希尔排序 B、冒泡排序 C、直接插入排序 D、直接选择排序2、没有1000个无序的元素、希望用最快的速度挑选出其中前10个最大的元素,最好的 排序法。A、冒泡排序 B、堆排序 C、快速排序 D、基数排序3、排序的元素序列基本有序的前提下，效率最高的排序方法是_ _ _ _ _ _A、直接插入排序 B、直接选择排序C、快速排序 D、归并排序4、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆 oA、79,46,56,38,40,80 B、84,79,56,38,40,46C、84,79,5

26、6,46,40,38 D、84,56,79,40,46,385、一组记录的关键码为(46,79,56,38,40,84),则利用快速排序方法，以第一个记录为基准得到的一次划分结果为A、38,40,46,56,79,84 B、40,38,46,79,56,84C、40,38,46,56,79,84 D、40,38,46,84,56,796、排序方法中，从未排序序列中依次取出元素与已排序(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置的方法，称为。A、希尔排序 B、归并排序 C、插入排序 D、选择排序7、用一种排序方法对线性表(25,84,21,47,15,27,68,35,20)进行

27、排序时，元素寻列的变化情况如下：初始：25,84,21,47,15,27,68,35,20第一趟:20,15 21,25,47,27,68,35,84第二趟：15,20,21,25,35,27,47,68,84第三趟：15,20,21,25,27,35,47,68,84则所采用的排序方法是。A、选择排序 B、希尔排序 C、归并排序 D、快速排序8、在一个具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度是。A、0(1)B、O(n)C、0(M)D、O(n l o g2n)9、给定n 个元素的向量，建立一个有序单链表的时间复杂度是 oA、O B、0(n)C、0(2)D、O(n l o

28、 g2n)二、解决下列问题1、已知序列(1 7,1 8,6 0,4 0,7,3 2,7 3,6 5,8 5),请给出采用冒泡排序法对该序列法对该序列作升序时每一趟的结果。2、已知序列(5 0 3,8 7,5 1 2,6 1,9 0 8,1 7 0,8 9 7,2 7 5,6 5 3,4 6 2),请给出采用堆排序法对该序列作升序排序时每一趟的结果。3、已知序列(5 0 3,8 7,5 1 2,6 1,9 0 8,1 7 0,8 9 7,2 7 5,6 5 3,4 6 2),请给出采用基数排序法对对该序列作升序排序时每一趟的结果。4、已知序列(5 0 3,1 7,5 1 2,9 0 8,1 7 0,8 9 7,2 7 5,6 5 3,4 2 6,1 5 4,5 0 9,6 1 2,6 7 7,7 6 5,7 0 3,9 4),请给出采用快速排序法对给序列作升序排序时每一趟的结果。