本课程讨论各种数据组织和处理中的数据逻辑结构，存储结构以及有关操作的算法分析和设计。结合课堂讲授和上机实验，使学生学会分析研究计算机所处理的数据结构的特性，以便为应用所涉及的数据选择适当的逻辑结构和存储结构，并对所处理的问题的数据结构进行分析、描述、算法设计以及编程实现。同时，还使学生初步掌握对算法的时间复杂度和空间复杂度进行分析的方法，进一步提高解决复杂抽象的现代数学问题的能力。
学堂在线北京交通大学数据结构与算法(2022春)作业题答案
第1章 绪论
- 线性结构中数据元素的位置之间存在( )的关系。 A一对多 B一对一 C多对多 D每一个元素都有一个直…
- 数据结构中,与所使用的计算机无关的是数据的( )结构。 A物理 B存储 C逻辑与物理 D逻辑…
- 以下说法正确的是( )。 A数据项是数据的基本单位 B数据元素是数据的最小单位 C数据结构是带结构…
- 数据元素是数据的基本单位,它( )。 A只能有一个数据项组成 B至少有二个数据项组成 C可以是一个数…
- 一种逻辑结构( )存储结构。 A可以有不同的 B只能有唯一的 C的数据元素在计算机中的表示称为 D的…
- 在数据结构中,从逻辑上可以把数据结构分为( )。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线…
- 数据结构在计算机内存中的表示是指( )。 A数据的存储结构 B数据结构 C数据的逻辑结构 D数据元素…
- 在数据结构中,与所使用的计算机无关的是数据的( )结构。 A逻辑 B存储 C逻辑和存储 D物理…
- 在存储数据时,通常不仅要存储各数据元素的值,而且还要存储( )。 A数据的处理方法 B数据元素的类…
- 在决定选取何种存储结构时,一般不考虑( )。 A各结点的值如何 B结点个数的多少 C对数据有哪些运算…
- 通常数据的逻辑结构包括____、____、____、____四种类型。
- 通常可以把一本含有不同章节的书的目录结构抽象成____结构。
- 通常可以把某城市中各公交站点间的线路图抽象成____结构。
- 结构中的数据元素存在多对多的关系称为____结构。
- 结构中的数据元素存在一对多的关系称为____结构。
- 把数据存储到计算机中,并具体体现数据之间的逻辑结构称称为物理____结构。…
- 把数据存储到计算机中,并具体体现数据之间的逻辑结构称为____结构。…
- 下面程序段的时间复杂度是____O________。 for( i =0; i
第2章 线性表
- 在以下的叙述中,正确的是( )。 A线性表的顺序存储结构优于链表存储结构 B二维数组是其数据元素为…
- 针对线性表,在存储后如果最常用的操作是取第i个结点及其前驱,则采用( )存储方式最节省时间。 A单…
- 通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着( )。 A数据元素具有同一特点 B不…
- 设有一个长度为n的顺序表,要在第i个元素之前(也就是插入元素作为新表的第i个元素),则移动元素个…
- 设顺序存储的线性表长度为n,对于插入操作,设插入位置是等概率的,则插入一个元素平均移动元素的次…
- 线性表的顺序结构中,( )。 A逻辑上相邻的元素在物理位置上不一定相邻 B数据元素是不能随机访问的…
- 链表所具备的特点是( )。 A可以随机访问任一结点 B占用连续的存储空间 C可以通过下标对链表进行…
- 线性表采用链式存储时,其地址( )。 A一定是不连续的 B必须是连续的 C可以连续也可以不连续 D部分…
- 在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除q所…
- 设有一个不带头结点的单向循环链表,结点的指针域为next,指针p指向尾结点,现要使p指向第一个结点,…
- 在双向链表中,每个结点有两个指针域,一个指向结点的直接后继,另一个指向____。…
- 设有一个头指针为head的单向循环链表,p指向链表中的结点,若p->next==____,则p所指结点为尾结点。…
- 设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->next==NULL,通过操作____p->next=h…
- 设有一个单向循环链表,结点的指针域为next,头指针为head,指针p指向表中某结点,若逻辑表达式____p…
- 设有一个单向循环链表,头指针为head,链表中结点的指针域为next,p指向尾结点的直接前驱结点,若要…
- 要在一个带头结点的单向循环链表中删除头结点,得到一个新的不带头结点的单向循环链表,若结点的指…
- 设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->next= =NULL,通过操作____p->next=…
- 双向循环链表中,p指向表中某结点,则通过p可以访问到p所指结点的直接后继结点和直接前驱结点,这种…
- 设有一个单向链表,结点的指针域为next,头指针为head,p指向尾结点,为了使该单向链表改为单向循环…
第3章 栈和队列
- 以下说法正确的是( )。 A栈的特点是先进先出,队列的特点是先进后出 B栈和队列的特点都是先进后出…
- 栈和队列的相同点是( )。 A都是后进先出 B都是后进后出 C逻辑结构与线性表不同 D逻辑结构与线性…
- 一个栈的进栈序列是a,b,c,d,e,则栈的不可能的输出序列是( )。 Aedcba Bdecba Cdceab Dabcde…
- 设有一个栈,元素依次进栈的顺序为A、B、C、D、E。下列( )是不可能的出栈序列。 AA,B,C,D,E BB,C,…
- 以下( )不是队列的基本运算? A从队尾插入一个新元素 B从队列中删除第i个元素 C判…
- 元素3,6,9按顺序依次进栈,则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A9,3,6 B9,6,3 …
- 元素2,4,6,8按顺序依次进栈,则该栈的不可能输出序列是( )(进栈出栈可以交替进行)。 A8,6,4,2 B2,…
- 一个栈的进栈序列是5,6,7,8,则栈的不可能的出栈序列是( )(进出栈操作可以交替进行) A5,8,6,7 B7,…
- 一个栈的进栈序列是efgh,则栈的不可能的出栈序列是( )(进出栈操作可以交替进行)。 Ahgfe Bgfeh C…
- 从一个栈顶指针为h的链栈中删除一个结点时,用x保存被删结点的值,可执行x=h->data;和____h=h->nex…
- 向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行____s->next=h;____和h=s;。 3.从一个栈顶…
- 设有一个非空的链栈,栈顶指针为hs,要进行出栈操作,用x保存出栈结点的值,栈结点的指针域为next,数…
- 设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈,则可执行操作s-> next=hs; ____hs=s;__…
- 设有一个非空的链栈,栈顶指针为hs,要进行出栈操作,用x保存出栈结点的值,栈结点的指针域为next,则…
- 设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈,则可执行操作____s->next=hs;____和hs=…
- 在一个链队中,设f和r分别为队头和队尾指针,则插入s所指结点的操作为____r->next=s;____和r=s; (…
- 在一个链队中,f和r分别为队头和队尾指针,队结点的指针域为next,s指向一个要入队的结点,则入队操…
- 栈和队列的操作特点分别是____和 ____。
第4章 串
- 在C语言中,顺序存储长度为3的字符串,需要占用( )个字节。 A3 B4 C6 D12
- 串的长度是指( )。 A串中所含不同字母的个数 B串中所含字符的个数 C串中所含不同字符的个数 D串…
- 串是一种特殊的线性表,其特殊性体现在( )。 A可以顺序存储 B数据元素是一个字符 C可以链式存储 D…
- 设有两个串p和q,求q在p中首次出现的位置的运算称为( )。 A连接 B模式匹配 C求子串 D求串长…
- 串函数StrCmp(“d”,“D”)的值为( )。 A0 B1 C-1 D3
- 串函数StrCmp(“abA”,”aba”)的值为( )。 A1 B0 C“abAaba” D-1
- char *p; p=StrCat(“ABD”,”ABC”); Printf(“%s”,p); 显示结果为( )。 A-1 BABDABC CAB D1…
- 两个串相等的充分必要条件是____。
- 串的两种最基本的存储方式是____和 ____。
- A‘在存储时占____个字节。 “A”在存储时占____个字节。
- 顺序存储字符串“ABCD”需要占用____个字节。
- 程序段 int count=0; char *s=” ABCD”; while(*s!=’’){s++;count++;} 执行后count= ____…
- 程序段 char *s=”aBcD”;n=0; while(*s!=’’) { if(*s>=’a’&&*s<=’z’)n++; s++; } 执行…
第5章 数组和广义表
- 设有一个10阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主存储到一维数组B中(数组…
- 设有一个15阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数…
- 设有一个15阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵…
- 对矩阵进行压缩存储是为了( )。 A方便运算 B方便存储 C提高运算速度 D减少存储空间…
- 稀疏矩阵存储时,采用一个由____ 、____ 、____3部分信息组成的三元组唯一确定矩阵中的一个非零元…
- 设有n阶对称矩阵A,用数组S进行压缩存储,当i____。(数组元素的下标从1开始)…
- ‘A‘在存储时占____个字节。 “A”在存储时占____个字节。 6.顺序存储字符串“ABCD”需要占用__…
第6章 树和二叉树
- 在一棵二叉树中,若编号为i的结点存在右孩子,则右孩子的顺序编号为( )。 A2i B2i-1 C2i+2 D2i+1…
- 一棵完全二叉树共有30个结点,则该树一共有( )层(根结点所在层为第一层)。 A6 B4 C3 D5…
- 设一棵哈夫曼树共有n个叶结点,则该树有( )个非叶结点。 An-1 Bn Cn+1 D2n…
- 一棵哈夫曼树有12个叶子结点(终端结点),该树总共有( )个结点。 A22 B21 C23 D24…
- 如下图所示,若从顶点a出发按深度优先搜索法进行遍历,则可能得到的顶点序列为( )。 …
- 如图若从顶点a出发按广度优先搜索法进行遍历,则可能得到的顶点序列为( )。 Aace…
- 如图若从顶点a出发按深度优先搜索法进行遍历,则可能得到的顶点序列为( )。 Aacf…
- 一棵哈夫曼树总共有23个结点,该树共有( )个叶结点(终端结点) A10 B13 C11 D12…
- 设一棵有n个结点采用链式存储的二叉树,则该树共有( )个指针域为空。 A2n Bn+1 C2n+1 D2n+2…
- 对一个满二叉树,m个叶子,n个结点,深度为h,则( )。 Ah+m = 2n Bm = h-1 Cn = 2h-1…
- 一棵二叉树中顺序编号为5的结点(树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同…
- 一棵二叉树没有单分支结点,有6个叶结点,则该树总共有____个结点。
- 一棵有n个叶结点的二叉树,其每一个非叶结点的度数都为2,则该树共有____个结点。…
- 一棵有2n-1个结点的二叉树,其每一个非叶结点的度数都为2,则该树共有____个叶结点。 【 】…
- 一棵有14个结点的完全二叉树,则它的最高层上有____个结点。
- 一棵二叉树叶结点(终端结点)数为5,单分支结点数为2,该树共有____个结点。…
- 二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说…
- 一棵二叉树总结点数为11,叶结点数为5,该树有____个双分支结点,____个单分支结点。…
- 深度为k的二叉树最多有____结点。 :. 一棵有n个叶结点的二叉树,其每一个非叶结点的度数都为2,则…
第7章 图
- 在一个无向图中,所有顶点的度数之和等于边数的( )倍。 A3 B2.5 C1.5 D2
- 已知一个图的边数为m,则该图的所有顶点的度数之和为( )。 A2m Bm C2m+1 Dm/2…
- 已知一个图的所有顶点的度数之和为m,则该图的边数为( )。 A2m Bm C2m+1 Dm/2…
- 以下说法不正确的是( )。 A连通图G一定存在生成树 B连通图G的生成树中一定包含G的所有顶点 C连通…
- 以下说法不正确的是( )。 A连通图G的生成树一定是唯一的 B连通图G一定存在生成树 C连通图G的生成…
- 采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。 A先序遍历 B中序遍历 C后序遍历 D按…
- 采用邻接表存储的图的广度优先遍历算法类似于二叉树的( )。 A先序遍历 B中序遍历 C后序遍历 D按…
- 具有n个结点的连通图至少有( )条边。 An-1 Bn Cn(n-1)/2 D2n
- 已知如图1所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的一种顶点序列为( )…
- 已知如图1所示的一个图,若从顶点V1出发,按广度优先进行遍历,则可能得到的一种顶点序列为( )。 …
- 根据搜索方法的不同,图的遍历有____、 ____ 两种方法
- 图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是____的。(回答正确或不正确)…
第8章 查找
- 对线性表进行折半查找时,要求线性表必须( )。 A以顺序方式存储 B以顺序方式存储,且结点按关键字…
- 采用折半查找法查找长度为n的线性表时,每个元素的平均查找长度为( )。 AO(n2) BO(nlog2n) CO(n) …
- 在有序表{2,4,7,14,34,43,47,64,75,80,90,97,120}中,用折半查找法查找值80时,经( )次比较后查找…
- 有一个长度为10的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为( )…
- 采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法),最坏的情况下要进行( )次…
- 有序表为{1,2,4,6,10,18,20,32},用课本中折半查找算法查找值18,经( )次比较后成功查到。 A3 B2 C…
- 用折半查找法,对长度为12的有序的线性表进行查找,最坏情况下要进行( )次元素间的比较 A4 B3 C5 D…
- 顺序查找法适合于存储结构为( )的线性表。 A散列存储 B顺序存储或链式存储 C压缩存储 D索引存储…
- 对长度为n的线性表进行顺序查找,在等概率情况下,平均查找长度为( )。 An B(n+1)/2 C2n Dn-1…
- 以下说法错误的是( )。 A散列法存储的思想是由关键字值决定数据的存储地址 B散列表的结点中只包…
- 折半查找只适用于____存储的有序表 。
- 哈希函数是记录关键字值与该记录____之间所构造的对应关系。
- 二叉树排序中任一棵子树都是二叉排序树,这种说法是____的。(回答正确或不正确)…
- 哈希函数是记录关键字值与该记录存储地址之间所构造的____对应关系____。…
- 以下函数在a[0]到a[n-1]中,用折半查找算法查找关键字等于k的记录,查找成功返回该记录的下标,失败…
第9章 排序
- 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位…
- 在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A希尔排序 …
- 以下排序算法中，在一趟排序过程中，除了其它相关操作外，只进行一次元素间的交换的算法是（ ）。 …
- 排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少…
- 排序方法中，从尚未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ …
- 排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适…
- 在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束…
- 一组记录的关键字序列为（ 37， 70， 47， 29， 31， 85），利用快速排序，以第一个关键字为分割元素，经过一次划分后…
- 按某关键字对记录序列排序， 若 在排序前和排序后仍保持它们的前后关系，____ 则排序算法是稳定的，否…
