当前位置：文档之家 › 李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(串)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(串)

  • 格式：pdf
  • 大小：409.09 KB
  • 文档页数：11

下载文档原格式

  / 11

合集下载

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(线性表)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(线性表)

（10）以下关于链表的叙述中，不正确的是______。 A．结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B．逻辑上相邻的元素物理上不必相邻 C．可以通过计算直接确定第 i 个结点的存储地址 D．插入、删除运算操作方便，不必移动结点 【答案】C 【解析】链表每个元素的存储地址是随机分配的，通过指针相连接，因此不能通过结算 直接缺点第 i 个结点的位置。
项；插入和删除操作不需要移动元素，则必须采取链表存储结构。
（12）不带头结点的单链表 head 为空的判定条件是______。 A．head=NULL B．head->next=NULL C．head->nex=head D．head!=NULL 【答案】A 【解析】由于单链表不带有头结点，其头指针所指向的元素即为第一个元素，因此只要 判断头指针指向元素为 NULL 即可知链表为空。
3 / 29
圣才电子书 十万种考研考证电子书、题库视频学习平台

杂，也不能实现随机读取元素，同时存储密度较低因而浪费存储空间。
（7）当线性表采用链表存储时，其存放元素的单元地址______。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 【答案】D 【解析】线性表的采用链表存储，用指针记录对应元素的位置，对元素的存储位置没有 任何要求。
（13）某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点， 故采用______存储方式最节省运算时间。
2 / 29
圣才电子书

为 Ο（n），D 项错误。
十万种考研考证电子书、题库视频学习平台
（5）将两个各有 n 个元素的递增有序顺序表归并成一个有序顺序表，其最少的比较次 数是______。
数据结构教程李春葆课后答案第4章串

数据结构教程李春葆课后答案第4章串


8. 采用顺序结构存储串，设计一个实现串通配符匹配的算法 pattern_index()，其中的 通配符只有‘？’ ，它可以和任一个字符匹配成功。例如，pattern_index("？re"，"there are") 返回的结果是 2。 解：采用 BF 算法的穷举法的思路，只需要增加对‘?’字符的处理功能。对应的算法 如下：
void maxsubstr(SqString s,SqString &t) { int maxi=0,maxlen=0,len,i,j,k; i=0; while (i<s.length) //从下标为 i 的字符开始 { j=i+1; //从 i 的下一个位置开始找重复子串 while (j<s.length) { if (s.data[i]==s.data[j]) //找一个子串,其起始下标为 i,长度为 len { len=1; for(k=1;s.data[i+k]==s.data[j+k];k++) len++; if (len>maxlen) //将较大长度者赋给 maxi 与 maxlen { maxi=i; maxlen=len; } j+=len; } else j++; } i++; //继续扫描第 i 字符之后的字符 } t.length=maxlen; //将最长重复子串赋给 t for (i=0;i<maxlen;i++) t.data[i]=s.data[maxi+i]; }
SqString CommChar(SqString s1,SqString s2) { SqString s3; int i,j,k=0; for (i=0;i<s1.length;i++) { for (j=0;j<s2.length;j++) if (s2.data[j]==s1.data[i]) break; if (j<s2.length) //s1.data[i]是公共字符 { s3.data[k]=s1.data[i]; k++; } } s3.length=k; return s3; }
李春葆《数据结构教程》(第4版)课后习题-串(圣才出品)

李春葆《数据结构教程》(第4版)课后习题-串(圣才出品)

第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是2。

答：本题的基础是Brute—Force模式匹配算法，只是增加了“？”的处理功能。

对应的算法如下：2．有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。

答：扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。

最后返回s3串。

对应的算法如下：3．设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。

（1）计算模式P的nextval函数值。

（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。

答：（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。

表4-1 计算next数组和nextval数组（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：第1趟匹配：此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：第2趟匹配：此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：第3趟匹配：此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。

因j=-1，执行i=i+1=7，j=j+1=0，即：第4趟匹配：此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。

上机实验题4实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；（2）输出串s；（3）输出串s的长度；（4）在串s的第9个字符位置插入串s1而产生串s2；（5）输出串s2；（6）删除串s第2个字符开始的5个字符而产生串s2；（7）输出串s2；（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；（9）输出串s2；（10）提取串s的第2个字符开始的10个字符而产生串s3；（11）输出串s3；（12）将串s1和串s2连接起来而产生串s4；（13）输出串s4。

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(外排序)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(外排序)

第10章外排序一、单项选择题（1）以下关于外排序的叙述正确的是______。

A．外排序把外存文件调入内存，再利用内排序方法进行排序，所以外排序所花的时间完全由采用的内排序确定B．外排序所花的时间=内排序时间+外存信息读／写时间+内部归并所花的时间C．外排序并不涉及文件的读／写操作D．外排序完全可以由内排序来替代【答案】B【解析】外排序所花的时间由内排序时间、外存读写时间、内部归并时间三部分时间构成，因此AC两项错误，B项正确；外排序要将文件读取到内存中进行排序，但是由于文件大小可能会大于内存的最大容量，因此外排序不能完全由内排序替代。

（2）如果将一个由置换-选择排序得到的输出文件F1（含所有初始归并段）作为输入文件再次进行置换-选择排序，得到输出文件F2（含所有初始归并段），则F1和F2的差异是______。

A．F2中归并段的个数减少B．F2中归并段的最大长度增大C．F2和F1无差异D ．归并段个数及各归并段长度均不变，但F 2中可能存在与F 1不同的归并段【答案】C 【解析】当进行一次置换-选择排序后，文件的归并段即达到理想状态，无论再进行多少次排序，均不会发生变化，因此答案为C 项。

（3）采用败者树进行k 路平衡归并的外排序算法，其总的归并效率与k______。

A ．有关B ．无关【答案】A【解析】利用败者树进行k 路平衡归并不会影响总共需要的关键字比较次数，但是随着k 的增大，归并树的高度会减小，磁盘读/写的次数也就相应减少，从而提高总的归并效率，因此答案为A 项。

（4）对m 个初始归并段实施k 路平衡归并排序，所需的归并趟数是______。

A ．1B ．m/kC ．/m k ⎡⎤⎢⎥D ．log k m ⎡⎤⎢⎥【答案】D【解析】采用k 路归并，相应的归并树就有log k m ⎡⎤⎢⎥+1层，则需要归并的趟数为log k m ⎡⎤⎢⎥，答案为D 项。

（5）设有100个初始归并段，如果采用k 路平衡归并3趟完成排序，则k 值最小是______。

数据结构教程李春葆课后答案第10章内排序

数据结构教程李春葆课后答案第10章内排序


2 else d=d/3; } }
数据结构教程学习指导
（1）指出fun(a，n)算法的功能。 （2）当a[]={5，1，3，6，2，7，4，8}时，问fun(a，8)共执行几趟排序，各趟的排序 结果是什么？ 答：（1）fun(a，n)算法的功能是采用增量递减为1/3的希尔排序方法对a数组中元素进 行递增排序。 （2）当a[]={5，1，3，6，2，7，4，8}时，执行fun(a，8)的过程如下： d=2：2 1 3 6 4 7 5 8 d=1：1 2 3 4 5 6 7 8 共有两趟排序。 4. 在实现快速排序的非递归算法时，可根据基准元素，将待排序序列划分为两个子 序列。若下一趟首先对较短的子序列进行排序，试证明在此做法下，快速排序所需要的栈 的深度为 O(log2n)。 答：由快速排序的算法可知，所需递归工作栈的深度取决于所需划分的最大次数。在 排序过程中每次划分都把整个待排序序列根据基准元素划分为左、右两个子序列，然后对 这两个子序列进行类似的处理。 设S(n)为对n个记录进行快速排序时平均所需栈的深度， 则： S(n)=
KeyType QuickSelect(RecType R[],int s,int t,int k) //在 R[s..t]序列中找第 k 小的元素 { int i=s,j=t; RecType tmp; if (s<t) //区间内至少存在 2 个元素的情况 { tmp=R[s]; //用区间的第 1 个记录作为基准 while (i!=j) //从区间两端交替向中间扫描,直至 i=j 为止 { while (j>i && R[j].key>=tmp.key) j--; //从右向左扫描,找第 1 个关键字小于 tmp 的 R[j] R[i]=R[j]; //将 R[j]前移到 R[i]的位置 while (i<j && R[i].key<=tmp.key) i++; //从左向右扫描,找第 1 个关键字大于 tmp 的 R[i] R[j]=R[i]; //将 R[i]后移到 R[j]的位置 } R[i]=tmp; if (k-1==i) return R[i].key; else if (k-1<i) return QuickSelect(R,s,i-1,k); //在左区间中递归查找 else return QuickSelect(R,i+1,t,k); //在右区间中递&& s==k-1) return R[k-1].key; else return -1; }
数据结构教程李春葆课后答案第6章数组和广义表

数据结构教程李春葆课后答案第6章数组和广义表

答：对于上三角部分或者主对角中的元素 A[i][j（] i≤j），按列为主序存储时，前面有 0～ j-1 共 j 列，第 0 列有 1 个元素，第 1 列有 2 个元素，…，第 j-1 列有 j 个元素，所以这 j 列的元素个数=1+2+…+j=j(j+1)/2；在第 j 列中，A[i][j]元素前有 A[0..i-1，j]共 i 个元素。所 以 A[i][j]元素前有 j(j+1)/2+i 个元素，而 B 的下标从 0 开始，所以 A[i][j]在 B 中的位置 k=j(j+1)/2+i。
int length; }
//元素值 //重复元素的个数
如数组 A[]={1，1，1，5，5，5，5，3，3，3，3，4，4，4，4，4，4}，共有 17 个元 素，对应的压缩存储 B 为：{1，3}，{5，4}，{3，4}，{4，6}}。从中看出，如果重复元素 越多，采用这种压缩存储方式越节省存储空间。
6. 利用三元组存储任意稀疏数组 A 时，假设其中一个元素和一个整数占用的存储空间 相同，问在什么条件下才能节省存储空间。
答：设稀疏矩阵 A 有 t 个非零元素，加上行数 rows、列数 cols 和非零元素个数 nums （也算一个三元组），那么三元组顺序表的存储空间总数为 3(t+1)，若用二维数组存储时占 用存储空间总数为 m×n，只有当 3(t+1)<m×n 即 t<m×n/3-1 时，采用三元组存储才能节省存 储空间。
解：对于稀疏矩阵三元组表 a，从 a.data[0]开始查看，若其行号等于列号，表示是一
个对角线上的元素，则进行累加，最后返回累加值。算法如下：
bool diagonal(TSMatrix a,ElemType &sum)
李春葆《数据结构教程》(C++语言描述)课后习题(第9~11章)【圣才出品】

李春葆《数据结构教程》(C++语言描述)课后习题(第9~11章)【圣才出品】

（6）有一组数据{15，9，7，8，20，-1，7，4}，用堆排序的筛选方法建立的初始堆 为______。
A．{-1,4,8,9,20,7,15,7} B．{-1,7,15,7,4,8,20,9} C．{-1,4,7,8,20,15,7,9} D．以上都不对 【答案】C 【解析】按照堆排序的筛选方法建立的初始堆必然满足堆的特点，且第一个元素为最大 （堆为大根堆时）或最小（堆为小根堆时）的元素，由这一特点可知，AB 项错误，而 C 项 满足条件，因此答案为 C 项。
不正确，因此至少需要进行的趟数是 5，答案为 C 项。
（8）对 8 个元素的顺序表进行快速排序，在最好情况下，元素之间的比较次数为______ 次。
A．7 B．8 C．12 D．13 【答案】D 【解析】当元素随机排序时，且每次选取参考元素均为其中值时，快速排序呈现最好的 状况。在 8 个元素的情况下，设这 8 个元素为 0-7，则比较 7 次的元素为 4，比较 3 次的元 素为 2，比较 2 次的元素为 6，比较 1 次的元素为 1，其余各元素在以其他元素为基准进行 比较时位置已经确定，因此需要进行比较的次数为：7+3+2+1=13，答案为 D 项。
（10）数据序列{3，2，4，1，5，6，8，7}是第一趟递增排序后的结果，则采用的排 序方法可能是______。
A．快速排序 B．冒泡排序 C．堆排序 D．简单选择排序 【答案】A 【解析】从得到的序列可以看出，元素 5 被正确归位，且其之前的元素均比其小，之 后的元素均比其大，满足快速排序的特点，因此 A 项是有可能的。BCD 三项均会产生全局 有序区，与已知序列不符，因此答案为 A 项。
（11）以下关于快速排序的叙述正确的是______。 A．快速排序在所有排序方法中最快，而且所需辅助空间最少 B．在快速排序中，不可以用队列替代栈
数据结构教程李春葆课后答案 图

数据结构教程李春葆课后答案 图

（3）对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素为1的个数；对于邻接矩 阵表示的有向图，顶点i的出度等于第i行中元素为1的个数，入度等于第i列中元素为1的个 数，顶点i度等于它们之和。
对于邻接表G表示的无向图，顶点i的度等于G->adjlist[i]为头结点的单链表中边表结点 个数。
对于邻接表G表示的有向图，顶点i的出度等于G->adjlist[i]为头结点的单链表中边表结 点的个数；入度需要遍历所有的边结点，若G->adjlist[j]为头结点的单链表中存在编号为i 的边结点，则顶点i的入度增1，顶点i的度等于入度和出度之和。
4
数据结构教程学习指导
中。因为在采用Kruskal算法构造最小生成树时，选择这3条权最小的边加入时，有可能出 现回路。例如，如图8.5所示的带权无向图，有3条边的权均为1，它们一定不会同时都出现 在其任何最小生成树中。
1 1
1 0
1
3
3 2
图 8.5 一个带权无向图
8. 对于如图8.6所示的带权有向图，采用Dijkstra算法求出从顶点0到其他各顶点的最短 路径及其长度，要求给出求解过程。
0
0
1
2
4
5
1
2
4
5
6
3
6
(a) 一个有向图
3 (b) 3 个强连通分量
图 8.2 一个有向图及其强连通分量
3. 对于稠密图和稀疏图，采用邻接矩阵和邻接表哪个更好些？ 答：邻接矩阵适合于稠密图，因为邻接矩阵占用的存储空间与边数无关。邻接表适合 于稀疏图，因为邻接表占用的存储空间与边数有关。
4. 对 n 个顶点的无向图和有向图（均为不带权图），采用邻接矩阵和邻接表表示时， 如何求解以下问题：
李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(栈和队列)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(栈和队列)

（9）若一个栈用数组 data[1．．n]存储，初始栈顶指针 top 为 0，则以下元素 x 进栈 的正确操作是______。
A．top++；data[top]=x；
4 / 21
圣才电子书 十万种考研考证电子书、题库视频学习平台

B．data[top]=x；top++； C．top--；data[top]=x； D．data[top]=x；top--； 【答案】A 【解析】与上两题类似，此题中栈顶指针所指的元素为 i，而此时要进栈的元素在数组 中的位置为 data[i+1]，因此需要先修改栈顶指针令其加 1，再将元素放入数组中，答案为 A 项。
因此答案为 C 项。
（12）栈和队列的不同点是______。 A．都是线性表 B．都不是线性表 C．栈只能在一端进行插入、删除操作，而队列在不同端进行插入、删除操作 D．没有不同点 【答案】C 【解析】栈为先进后出，意味着其只能在一端进行插入、删除操作，而队列为先进先出， 意味着其可以不同端进行插入、删除操作，所以答案为 C 项。
3 / 21
圣才电子书 十万种考研考证电子书、题库视频学习平台

A．top++；data[top]=x； B．data[top]=x；top++； C．top--；data[top]=x； D．data[top]=x；top--； 【答案】C 【解析】元素 x 进栈时，需要先修改栈顶指针指向栈顶元素的位置，而由题干可知，此 栈的栈顶指针的值应为 n+1-i，其中 i 为栈中已有元素的个数，因此第一步需要先将栈顶指 针减 1，再将元素放入栈顶指针所指位置，因此答案为 C 项。
（6）表达式（a+a*b）*a+C*b／a 的后缀表达式是______。 A．a a b*+a*c b*a／+ B．a a*b+a*c b*a／+ C．a a b*a*c b*+a／+ D．a a b*+a c b*a／+* 【答案】A 【解析】按照表达式到后缀表达式的原则可知，答案为 A 项。
李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(查 找)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(查 找)

（9）含有 20 个结点的 AVL 树的最小高度是______。 A．4 B．5 C．6 D．7
4 / 14
圣才电子书

【答案】B
十万种考研考证电子书、题库视频学习平台
【解析】与（8）同理可知答案为 B 项。
（10）在一棵 rn-阶 B 树中，有 k 个孩子结点的非叶子结点恰好包含______关键字。 A．k+1 B．k C．k-1 D．m／2 【答案】C 【解析】按照 B-树的定义可知，有 k 个孩子结点的非叶子节点应该有 k-1 个关键字， 答案为 C 项。
大高度应为 log2 (2047 1) 1 12 ，答案为 B 项。
（13）在以下查找方法中，查找效率与记录个数 n 无直接关系的是______。 A．顺序查找 B．折半查找 C．哈希查找 D．二叉排序树查找 【答案】C 【解析】哈希查找时的平均查找长度不是元素个数 n 的函数，而是装填因子 a 的函数。 因此答案应为 C 项。
（2）在对线性表进行折半查找时，要求线性表必须______。 A．以顺序方式存储 B．以链接方式存储 C．以顺序方式存储，且结点按关键字有序排序 D．以链表方式存储，且结点按关键字有序排序 【答案】C 【解析】对线性表进行折半查找时要求线性表必须以顺序方式存储，且结点按关键字有
1 / 14
圣才电子书 十万种考研考证电子书、题库视频学习平台
（7）一棵二叉排序树是由关键字集合{18，43，27，44，36，39}构建的，其中序遍 历序列是______。
3 / 14
圣才电子书 十万种考研考证电子书、题库视频学习平台

A．树形未定，无法确定 B．18，43，27，77，44，36，39 C．18，27，36，39，43，44，77 D．77，44，43，39，36，27，18 【答案】C 【解析】二叉排序树的中序遍历即为有序递增序列，因此答案应为 C 项。
李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(树和二叉树)

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(树和二叉树)

第6章树和二叉树一、单项选择题（1）现有一“遗传”关系，设x是y的父亲，则x可以把他的属性遗传给y。

表示该遗传关系最适合的数据结构为______A．数组B．树C．图D．线性表【答案】B【解析】树是一种非线性数据结构，它的每一个结点可以有零个或多个后继结点，但有且只有一个前趋结点，这一特点正好与父子间的遗传关系相似，所以答案为B项。

（2）一棵高度为h、结点个数为n的m（m≥3）次树中，其分支数是______。

A．nhB．n+hC．n-1D．h-1【答案】C【解析】无论树的高度是多少，其分支数永远比节点数少1，因此答案为C项。

（3）若一棵三次树中有两个度为3的结点，一个度为2的结点，两个度为1的结点，该树一共有______个结点。

A．5B．8C．10D．11【答案】D【解析】结点的度即为该结点的孩子数，由题可知，此树共用孩子3×2+2×1+1×2=10个，又因为根节点不是任何结点的孩子，所以共有结点10+1=11个，答案为D项。

（4）若一棵有n个结点的二叉树，其中所有分支结点的度均为k，该树中的叶子结点个数是______。

A．n（k-1）／kB．n-kC．（n+1）／kD．（nk-n+1）／k【答案】D【解析】在分支结点度均为k的树中，每增加一个分支结点，可以增加（k-1）个叶子，假设该树的叶子结点数为x，则有(n-x)个分支结点，则这些分支结点增加的总叶子数为（k-1）×(n-x-1)+k，即可得到等式(k-1)×(n-x-1)+k =x，解得x=（nk-n+1）／k，答案为D项。

（5）以下关于二叉树的说法中正确的是______。

A．二叉树中每个结点的度均为2B．二叉树中至少有一个结点的度为2C．二叉树中每个结点的度可以小于2D．二叉树中至少有一个结点【答案】C【解析】二叉树的结点的度数不多于2，但是对于其具体的结点数并没有明确的要求，因此答案为C项。

李春葆《数据结构教程》(C++语言描述)课后习题(第5~8章)【圣才出品】


三、算法设计题 （1）设定二维整数数组 B[0..m-1，0..n-1]的数据在行、列方向上都按从小到大的顺序 排序，且整型变量 x 中的数据在 B 中存在。试设计一个算法，找出一对满足 B[i，j]=x 的 i、 j 值，要求比较次数不超过 m+n。 答： void FindX(int &a,int x) {
（4）一个稀疏矩阵经过压缩后，和直接采用二维数组存储相比会失去______特性。 A．顺序存储 B．随机存取 C．输入／输出 D．以上都不对 【答案】B 【解析】稀疏矩阵可以采用三元组顺序表或是十字链表压缩存储，无论采取哪种方式， 均会使稀疏矩阵不再具有随机存取功能，答案为 B 项。
（5）当 m 行 n 列的稀疏矩阵采用十字链表表示时，其中单链表的个数为______。
（3）简述广义表、数组和线性表之间的异同。 答：一维数组可以看做是一个线性表，类似的也可以采用链式存储和顺序存储结构，但 是在计算机中直接将其视为连续的存储单元集合，二维数组同理可以视为每一个元素都是相 同类型的线性表的线性表，以此类推，任何多维数组都可以看做是线性表，其中每一个数据 元素也是一个线性表，所以说多维数组是线性表的推广。 广义表也是线性表的推广，其一般表示业余线性表相同，只不过其每一个元素既可以是 一个线性表，也可以是一个单个数据元素（原子），而线性表中的每一个元素只能是单个的 数据，这也就使得广义表一般只能用链式结构来表示，二线性表可以用顺序结构和链式结构 表示。
答：下三角矩阵的示意图如下图所示：
4 / 73
圣才电子书

十万种考研考证电子书、题库视频学习平台
a00 a10a11 a20a31a32 aij a 1 ij
在 A[i,j]之前共有 i 行，每行元素个数递增，同时此行有 j 个元素在其之前，因此其前

李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(绪论)

第1章绪论一、单项选择题（1）计算机所处理的数据一般具备某种内在联系，这是指______。

A．数据和数据之间存在某种关系B．元素和元素之间存在某种关系C．元素内部具有某种结构D．数据项和数据项之间存在某种关系【答案】B【解析】数据是计算机操作对象的总称，数据元素是计算机处理数据的基本单位，因此数据之间的内在联系指的应该是数据元素和数据元素之间的关系。

（2）在数据结构中，与所使用计算机无关的是数据的______结构。

A．逻辑B．存储C．逻辑和存储D．物理【答案】A【解析】数据的逻辑结构是从逻辑关系上描述数据的，它与数据的存储无关，是独立于计算机的。

而数据的存储结构是指数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构，与计算机有关。

（3）数据结构在计算机中的表示称为数据的______。

A．存储结构B．抽象数据类型C．顺序结构D．逻辑结构【答案】A【解析】数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示。

（4）在计算机中存储数据时，通常不仅要存储各数据元素的值，还要存储______。

A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法【答案】C【解析】存储实现的基本目标是建立数据的机内表示，其包括两个部分，即数据元素的存储和数据元素之间关系的存储。

（5）在计算机的存储器中表示数据时，逻辑上相邻的两个元素对应的物理地址也是相邻的，这种存储结构称为______。

A．逻辑结构B．顺序存储结构C．链式存储结构D．以上都正确【答案】B【解析】顺序存储结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构。

所以答案B项正确；逻辑结构是独立于计算机的与存储结构相平行的概念，并不是存储结构的一种，A项错误；中链式存储结构不要求逻辑上相邻的结点在物理位置上也相邻，结点同的逻辑关系用附加的指针域来表示，C项错误。

数据结构教程李春葆课后答案第11章外排序

第11章外排序教材中练习题及参考答案1. 外排序中两个相对独立的阶段是什么？答：外排序中两个相对独立的阶段是产生初始归并段和多路归并排序。

2.给出一组关键字T=（12，2，16，30，8，28，4，10，20，6，18），设内存工作区可容纳4个记录，给出用置换-选择排序算法得到的全部初始归并段。

答：置换-选择排序算法的执行过程如表11.1所示。

共产生两个初始归并段，归并段1为（2，8，12，16，28，30），归并段2为（4，6，10，18，20）。

表11.1 初始归并段的生成过程3. 设输入的关键字满足k1>k2>…>k n，缓冲区大小为m，用置换-选择排序方法可产生多少个初始归并段？答：可产生⎡n/m⎤个初始归并段。

设记录R i的关键字为k i（1≤i≤n），先读入m个记录R1、R2、…、R m，采用败者树选择最小记录R m，将其输出到到归并段1，R min=k m，在该位置上读入R m+1，采用败者树选择最小记录R m-1，将其输出到到归并段1，R min=k m-1，在该位置上读入R m+2，采用败者树选择最小记录R m－2，将其输出到到归并段1，R min=k m-2，…，以此类推，产生归并段1：（R m，R m-1，…，R1）。

同样产生其他归并段（R2m，R2m-1，…，R m+1），（R3m，R3m-1，…，R2m+1），…，一共有⎡n/m⎤个初始归并段。

4. 什么是多路平衡归并，多路平衡归并的目的是什么？答：归并过程可以用一棵归并树来表示。

多路平衡归并对应的归并树中，每个结点都是平衡的，即每个结点的所有子树的高度相差不超过1。

k路平衡归并的过程是：第一趟归并将m个初始归并段归并为⎡m/k⎤个归并段，以后每一趟归并将l个初始归并段归并为⎡l/k⎤个归并段，直到最后形成一个大的归并段为止。

m个归并段采用k路平衡归并，总的归并趟数s=⎡log k m⎤。

其趟数是所有归并方案中最少的，所以多路平衡归并的目的是减少归并趟数。

李春葆编著数据结构(C语言篇)习题与解析(修订版)

一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取B.顺序存取C.索引存取D.散列存取5.算法分析的目的是1，算法分析的两个主要方面是2。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

A.正确B.不正确填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。

(NEW)李春葆《数据结构教程》(C++语言描述)配套题库【名校考研真题+课后习题+章节题库+模拟试题】

A．DIV R0，R1；（R0）/（R1）→R0 B．INT n；产生软中断 C．NOT R0；寄存器R0的内容取非 D．MOV R0，addr；把地址处的内存数据放入寄存器R0中 【答案】C 【解析】A项，除法操作出现除数为零的情况时，会产生内中断， CPU切换为内核态进行中断处理；B项，直接产生中断，会切换到内核 态；D项，addr出现非法地址，会出现中断，进而切换到内核态。
D．1用C语言写的某单位的认识管理程序语言，2操作系统，3编译
程序 【答案】B 【解析】计算机系统的组成如下图所示：
其中，C语言写的某单位的认识管理程序语言属于应用程序，编译 程序属于语言处理程序。
3 假定下列指令已装入指令寄存器。则执行时不可能导致CPU从 用户态变为内核态（系统态）的是（ ）。[2015年联考真题]
5 下列说法中( )不是创建进程必须的。[上海交通大学考研真 题]
A．建立一个进程的进程表项 B．为进程分配内存 C．为进程分配CPU D．将进程表项放入就绪队列 【答案】C 【解析】进程刚被创建后，实际上是处于就绪状态的，所以不许为 进程分配CPU。
6 若系统S1采用死锁避免方法，S2采用死锁检测方法，下列叙述 中正确的是（ ）。[2015年联考真题]
4 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。 [2015年联考真题]
A．执行P（wait）操作 B．申请内存失败 C．启动I/0设备 D．被高优先级进程抢占 【答案】D 【解析】D项，被高优先级进程抢占，进程会由执行态变为就绪 态。ABC三项，程序由于缺少资源而由执行态转为阻塞态。
目录
第一部分 名校考研真题 一、选择题 二、综合应用题
第二部分 课后习题 第1章 绪 论 第2章 线性表 第3章 栈和队列 第4章 串 第5章 数组和广义表 第6章 树和二叉树 第7章 图 第8章 查 找 第9章 内排序 第10章 外排序 第11章 数据结构和STL

李春葆《数据结构教程》(C++语言描述)配套题库【章节题库】(内排序)

第9章内排序一、选择题1．排序算法的稳定性是指（）。

A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变C．算法的排序性能与被排序元素的数量关系不大D．算法的排序性能与被排序元素的数量关系密切【答案】A【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

2．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）。

A．选择排序法B．插入排序法C．快速排序法D．堆排序法【答案】A【解析】选择排序的基本思想是：第i趟排序开始时，当前有序区和无序区分别为R[0．．i-1]和R[i．．n-1]（______0≤i<n-1），该趟排序则是从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[0．．i]和R[i+1．．n-1]分别变为新的有序区和新的无序区。

3．设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（）。

A．O（N），O（N），O（N）B．O（N），O（N*log2N），O（N*log2N）C．O（N），O（N*log2N），O（N2）D．O（N2），O（N*log2N），O（N2）【答案】C【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O（N）。

对于采用归并法，它是一种稳定的排序方法，它的时间复杂度为O（Nlog2N）。

对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为O（N2）。

4．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

{
i=ch-'A'+10;
num[i]++;
}
}
（2）设计一个算法，将一个链串 S 中的所有子串”abc”删除。 答： String deleteabc(String S) {
String t=’abc’; String nstr; int i=0,j=0,k=0;
6 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
（2）以下______是“abcd32lABCD”串的子串。 A．abcd B．B21AB C．”abcABC” D．“21AB” 【答案】D 【解析】串需要用引号引起来，没有引号的只是字符的罗列而不是串，因此 AB 项错误； 由在一个串中由任意连续的字符组成的子序列称为该串的子串可知，C 项中字符串并不包含
②对于模式串 t（t=t0t1…tm-1），求 next 数组时，next[i]在什么条件下取-1。 答：当 i=0 时，即 next[0]=-1。
（4）设目标串为 s=“abcaabbcaaabababaabca”，模式串为 p=“babab”。 ①计算模式 P 的 答：-1,0,1,2,0。 ②不写算法，只画出利用 KMP 算法进行模式匹配时的每一趟的匹配过程。
二、问答题 （1）若 s1 和 s2 为串，给出使 s1//s2=s2//s1 成立的所有可能的条件（其中，“//” 表示两个串连接的运算符）。 答：①s1 和 s2 之中至少有一个为空串 ②s1 和 s2 的值相等 ③s1 和 s2 之中某一个串可由另一个串经过重复得到。
3 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
1 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台

于主串中，因此答案为 D 项。
（3）对于一个链串 s，查找第一个元素值为 x 的算法的时间复杂度为______。 A．O（1） B．O（n） C．O（n2） D．以上都不对 【答案】B 【解析】在链串中按值查找元素时，最坏的情况是每一个元素都需要从头开始逐一查找， 因此其时间复杂度为 O（n），B 项正确。

（2）在 KMP 算法中计算模式串的 next，当 j=0 时，为什么要取 next[0]=-1？ 答：若将 next[0]的值设置为 0，由于在 KMP 算法中匹配失败进行回溯时，要回溯到 next[ j]=j 的位置，则每一次回溯都会回溯到 next[0]处，这样使得 KMP 算法失去了其意义， 因此要取 next[0]=-1；
5 / 11
圣才电子书

num[i]=0;
十万种考研考证电子书、题库视频学习平台
while((ch=getchar()))
{
if(('0'<=ch)&&(ch<='9'))
{
i=ch-'0';
num[i]++;
}
else if(('A'<= ch)&&(ch <='Z'))
（5）设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作______。 A．连接
2 / 11
圣才电子书

B．模式匹配
十万种考研
【答案】B
【解析】由模式匹配的定义可知，这种操作叫做模式匹配。
（6）已知 t=“abcaabbcabcaabdab”，该模式串的 next 数组值为______。 A．-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1 B．0,1,0,0,1,1,2,0,0,1,2,3,4,5,6,0,1 C．-1,0,0,0,1,1,2,0,0,1,2,3,4,5,6,7,1 D．-1,0,0,0,1,1,2,3,0,1,2,3,4,5,6,0,1 【答案】A 【解析】next 数组中存放的值为该模式串每个字符的部分匹配信息，即每一个字符前 有多少个字符与模式串开始的字符相同，由此定义可知，该模式串的 next 数组值应为 A 项。
（3）在串的模式匹配中，KMP 匹配算法是有用的办法，回答以下问题： ①KMP 算法的基本思想是什么？ 答：KMP 算法的思想是，设 s 为目标串、t 为模式串，并设 i 指针和 j 指针分别指示目 标串和模式串中待比较的字符，令 i 和 J 的初值均为 0。若有 si=tj，则 i 和 j 分别增 1；否则， i 不变，j 退回到 j=next[ j]的位置（即模式串右滑），比较 si 和 tj，若相等则指针各增 1．否 则 j 再退回到下一个 j=next[ j]的位置（即模式串继续右滑），再比较 si 和 tj。依此类推，直 到出现下列两种情况之一，一种情况是 j 退回到某个 J=next[ j]位置时有 si=tj，则指针各增 1 后继续匹配；另一种情况是 j 退回到 j=-1 时，此时令 i、j 指针各增 l，即下一次比较 Si+1 和 t0。
（4）对于一个链串 s，查找第 i 个元素的算法的时间复杂度为______。 A．O（1） B．O（n） C．O（n2） D．以上都不对 【答案】B 【解析】在链串中查找第 i 个元素时，由于元素的位置不确定，最坏的情况为第 i 个元 素为最后一个元素，需要查找 n 次，因此其时间复杂度为 O（n），B 项正确。
圣才电子书 十万种考研考证电子书、题库视频学习平台

第4章 串
一、单项选择题 （1）串是一种特殊的线性表，其特殊性体现在______。 A．可以顺序存储 B．数据元素是单个字符 C．可以链接存储 D．数据元素可以是多个字符 【答案】B 【解析】串和线性表的唯一区别是串中的每个元素是单个字符，而线性表中的每个元素 可以是自定义的其他类型，因此答案为 B 项
4 / 11
圣才电子书

答：
十万种考研考证电子书、题库视频学习平台
三、算法设计题 （1）设计一个算法，计算一个顺序串 s 中每个字符出现的次数。 答： void CountFre() {
int i,num[36]; char ch; for(i=0;i<36;i++)