数据结构与算法
习题册
（课后部分参考答案）
《数据结构与算法》课程组
目录
目录
课后习题部分
第一章绪论 (1)
第二章线性表 (3)
第三章栈和队列 (5)
第四章串 (8)
第五章数组和广义表 (10)
第六章树和二叉树 (13)
第七章图 (16)
第九章查找 (20)
第十章排序 (23)
第一章绪论
一. 填空题
1. 从逻辑关系上讲，数据结构的类型主要分为集合、线性结构、树结构和图结构。
2. 数据的存储结构主要有顺序存储和链式存储两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和数据元素之间的关系。
3. 算法具有五个特性，分别是有穷性、确定性、可行性、输入、输出。
4. 算法设计要求中的健壮性指的是算法在发生非法操作时可以作出处理的特性。
二. 选择题
1. 顺序存储结构中数据元素之间的逻辑关系是由C表示的，链接存储结构中的数据元素之间的逻辑关系是由D表示的。
A 线性结构
B 非线性结构
C 存储位置
D 指针
2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是B。
A 树
B 图
C 线性表
D 集合
3. 算法指的是A。
A 对特定问题求解步骤的一种描述，是指令的有限序列。
B 计算机程序
C 解决问题的计算方法
D 数据处理
三. 简答题
1. 分析以下各程序段，并用大O记号表示其执行时间。
(1)(2)
i=1;k=0; i=1;k=0;
While(i {{ k=k+10*i; k=k+10*i; i++; i++; } }while(i<=n) ⑴基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ⑵基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 2. 设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}， R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。 其逻辑结构图如下所示，它是一种图结构。 3. 求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴A(x)=a n x n+a n-1x n-1+…+a1x+a0 ⑵A(x)=(…(a n x+a n-1)x+…+a1)x)+a0 根据算法的时间复杂度分析比较这两种算法的优劣。 第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。 第二章线性表 一. 填空题 1. 在顺序表中，等概率情况下，插入和删除一个元素平均需移动表长的一半个元素，具体移动元素的个数与表长和插入的位置有关。 2. 在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动n-i+1 个元素，删除第i（1≤i≤n）个元素时，需向前移动n-i个元素。 3. 在单循环链表中，由rear指向表尾，在表尾插入一个结点s的操作顺序是s->next =rear->next; rear->next =s; rear =s;；删除开始结点的操作顺序为q=rear->next->next; rear->next->next=q->next; delete q;。 二. 选择题 1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的，称之为：C A存储结构B逻辑结构C顺序存储结构D链式存储结构 2. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是： A A 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B 在第i个结点后插入一个新结点（1≤i≤n） C 删除第i个结点（1≤i≤n） D 将n个结点从小到大排序 3. 线性表L在B情况下适用于使用链式结构实现。 A需经常修改L中的结点值B需不断对L进行删除插入 CL中含有大量的结点D L中结点结构复杂 4.单链表的存储密度C A大于1 B等于1 C小于1 D不能确定 三. 判断题 1. 线性表的逻辑顺序和存储顺序总是一致的。F 2. 线性表的顺序存储结构优于链接存储结构。F 3. 设p，q是指针，若p=q，则*p=*q。F 4. 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。F 四. 简答题 1. 分析下列情况下，采用何种存储结构更好些。 (1)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 (2)如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 (3)描述一个城市的设计和规划。 ⑴应选用顺序存储结构。很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 ⑵应选用链式存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 ⑶应选用链式存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。 五. 算法设计 1. 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。 2. 线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 int insert (datatype A[],int *elenum,datatype x) /*设elenum为表的最大下标*/ {if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/ else {i=*elenum; while (i>=0 && A[i]>x) /*边找位置边移动*/ {A[i+1]=A[i]; i--; } A[i+1]=x; /*找到的位置是插入位的下一位*/ (*elenum)++; return 1; /*插入成功*/ } } O（n） 第三章栈和队列 一. 填空题 1. 设有一个空栈，栈顶指针为1000H，现有输入序列为1. 2. 3. 4. 5，经过push，push，pop，push，pop，push，push后，输出序列是23 ，栈顶指针为1003H。 2. 栈通常采用的两种存储结构是顺序栈、链栈；其判定栈空的条件分别是TOP=-1、TOP=NULL，判定栈满的条件分别是TOP=数组长度、存储空间满。 3. 栈可作为实现递归函数调用的一种数据结构。 4. 表达式a*(b+c)-d的后缀表达式是abc+*d-。 二. 选择题 1. 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是D。 A不确定Bn-i Cn-i-1 Dn-i+1 2. 设栈S和队列Q的初始状态为空，元素e1. e2. e 3. e 4. e 5. e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2. e4. e3. e 6. e5. e1，则栈S的容量至少应该是C。 A6B4C3 D 2 3. 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是C。 A 54321 B 45321 C 43512 D 12345 三. 判断题 1. 有n个元素依次进栈，则出栈序列有(n-1)/2种。F 2. 栈可以作为实现过程调用的一种数据结构。T 3. 在栈满的情况下不能做进栈操作，否则将产生“上溢”。T 4. 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。F 四. 简答题 1. 设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。 ⑴C，E，A，B，D ⑵C，B，A，D，E ⑴不能，因为在C、E出栈后，A一定在栈中，而且在B的下面，不可能先于B出栈 ⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。 2. 在操作序列push(1). push(2). pop. push(5). push(7). pop. push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示k入栈，pop表示栈顶元素出栈。） 栈顶元素为6，栈底元素为1。 3. 在操作序列EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。 队头元素为5，队尾元素为9。 4. 简述以下算法的功能（栈的元素类型SElemType为int）。 (1) status algo1(Stack S,int e) { Stack T; int d; InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e) Push(T,d); } while(!StackEmpty(T)){ Pop(T,d); Push(S,d); } }//S中如果存在e，则删除它。 (2) void algo2(Queue &Q) { Stack S; int d; InitStack(S); while(!QueueEmpty(Q)) { DeQueue(Q, d); Push(S, d); } while(!StackEmpty(S)) { Pop(S, d); EnQueue(Q, d); } }//队列逆置 五. 算法设计 1. 试写一个判别表达式中开、闭括号是否配对出现的算法 BOOL BracketCorrespondency(char a[]) { int i=0; Stack s; InitStack(s); ElemType x; while(a[i]){ switch(a[i]){ case '(': Push(s,a[i]); break; case '[': Push(s,a[i]); break; case ')': GetTop(s,x); if(x=='(') Pop(s,x); else return FALSE; break; case ']': GetTop(s,x); if(x=='[') Pop(s,x); else return FALSE; break; default: break; } i++; } if(s.size!=0) return FALSE; return TRUE; } 2. 假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。 Status SymmetryString(char* p) { Queue q; if(!InitQueue(q)) return 0; Stack s; InitStack(s); ElemType e1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2) return FALSE; } return OK; } 第四章串 一. 填空题 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)=20, “/”的字符定位的位置为3。 3. 若n为主串长，m为子串长，则串的经典模式匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 二. 选择题 1. 串是一种特殊的线性表，其特殊性体现在：（B ） A可以顺序存储B数据元素是一个字符 C可以链式存储D数据元素可以是多个字符 2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：（B ） A连接B模式匹配C求子串D求串长 3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串， subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：（D ） A ‘BCDEF’ B ‘BCDEFG’ C ‘BCPQRST’ D ‘BCDEFEF’ 4. 若串S=”software”，其子串的数目是（B）。 A8 B37 C36 D9 三. 计算题 1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’, 求： 1）Replace(s,’STUDENT’,q) 2）Concat(t,SubString(s,7,8))) 1、Replace(s,’STUDENT’,q)＝’I AM A WORKER’ 2、因为SubString(s,7,8)＝‘STUDENT’Concat(t,SubString(s,7,8)) ＝’GOODSTUDENT’ 四. 算法设计 1. 利用C的库函数strlen, strcpy（或strncpy）写一个算法void StrDelete(char *S,int t,int m) ，删除串S中从位置i开始的连续的m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均被删去。 提示：strlen是求串长(length)函数：int strlen(char s); //求串的长度 strcpy是串复制(copy)函数：char *strcpy(char to,char from); //该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。 void StrDelete(char *S, int i ,int m) { //串删除 char Temp[Maxsize];//定义一个临时串 if(i+m { strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中 strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 } else if(i+m>=strlen(S)&& i { strcpy(&S[i],"\0");//把位置i的元素置为'\0'，表示串结束 } } 第五章数组和广义表 一. 填空 1. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288；末尾元素A57的第一个字节地址为1282；若按行存储时，元素A14的第一个字节地址为1072；若按列存储时，元素A47的第一个字节地址为1276。 2. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元素值。。 3. 广义表((a), (((b),c)),(d))的长度是3，深度是4，表头是(a) ，表尾是(((b),c)),(d) 。 4. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是 Head(Head(Tail(LS)))。 二. 选择题 1. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为( A )。（无第0行第0列元素） A 16902 B 16904 C 14454 D 答案A, B, C均不对 2. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[ 1, n(n-1)/2 ]中，下三角部分中任一元素a i,j(i≤j), 在一维数组B中下标k的值是：( B ) A i(i-1)/2+j-1 B i(i-1)/2+j C i(i+1)/2+j-1 Di(i+1)/2+j 3. 一个n*n的对称矩阵，用压缩存储方法处理其对称性质后存储，则其容量为：( C )。 An*n Bn*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2 三. 计算题 1. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？写出计算过程。 (676-644)/1=32 A[2][2]的地址相对A[0][0]偏移量为32，则A[3][3]相较于A[0][0]的偏移量为 32*3/2=48 A[3][3]地址为48+644=692 2. 设A[9][9]是一个10*10对称矩阵，采用压缩存储方式存储其下三角部分，已知每个元素占用两个存储单元，其第一个元素A[0][0]的存储位置在1000，求下面问题的计算过程及结果： 给出A[4][5]的存储位置。 A[4][5]是上三角部分，所以存在 A [5] [4] 若以行序为主序，则地址为1000+2（5（1+5）/ 2+4）=1036 若以列序为主序，则地址为1000+2（4（10+7）/ 2+5）=1062 给出存储位置为1080的元素下标。 i(i+1)/2+j 或j(10+10-j+1)/2+i=40 得i=9，j=4或i=8 j=5，A [8] [5]或A [9] [4] 3. 一个稀疏矩阵如图所示，则对应的三元组线性表是什么？其对应的十字链表是什么？ 4. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。 ???? ??? ?? ? ? ???????????1616 635444313 1212221646) 1( 0 0 2 0 3 0 0 0 0 0 -1 5 0 0 0 0 四. 算法设计 1. 设计一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。 2. 若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小 值且又是第j列元素中最大值，则称此元素为该矩阵的一个鞍点。假设以二维数组存储 矩阵A，试设计一个求该矩阵所有鞍点的算法，并分析最坏情况下的时间复杂度 void Saddle(int A[m][n]) //A是m*n的矩阵,本算法求矩阵A中的马鞍点. {int max[n]={0}, //max数组存放各列最大值元素的行号,初始化为行号0; min[m]={0}, //min数组存放各行最小值元素的列号,初始化为列号0; i, j; for(i=0;i {for(j=0;j {if(A[max[j]][j] if(A[i][min[i]]>A[i][j]) min[i]=j; //修改第i行最小元素的列号. } for (i=0;i {j=min[i]; //第i行最小元素的列号 if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j]); } } }// Saddle 分析算法，外层for循环共执行m次，内层第一个for循环执行n次，第二个for循环 最坏情况下执行m次，所以，最坏情况下的时间复杂度为Ｏ(mn+mm)。 第六章树和二叉树 一. 填空题 1. 树是n（n≥0）结点的有限集合。在一棵空树中有0个元素；在一棵非空树中，有且仅有一个个根结点，其余的结点分成m（m＞0）个互不相交的集合，每个集合都是根结点的子树。 2. 一棵二叉树的第i（i≥1）层最多有2i-1个结点；一棵有n（n>0）个结点的满二叉树共有(n+1)/2个叶子结点和(n-1)/2个非终端结点。 3. 设深度为k的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是2k-1，最小值是2k-1。 4. 深度为k的二叉树中，所含叶子的个数最多为2k-1。 5. 在顺序存储的二叉树中编号为i和j的两个结点处在同一层的条件为： 二. 选择题 1. 前序遍历和中序遍历结果相同的二叉树是（D）。 A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树 2. 序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（D ）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 3. 完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（C ）。 A h B h+1 C h或h+1 D 任意 4. 在线索二叉树中，一个结点是叶子结点的充要条件为（C）。 A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左. 右线索标志均为0 D 左. 右线索标志均为1 5. 由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（C ）。 A 24 B 48 C 53 D 72 三. 简答题 1. 已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，请构造出此二叉树，并写出此树的后序遍历序列。 2. 将下图所示的树转换为二叉树， 3. 图5-17所示的二叉树转换为树或森林 4. 已知某字符串S 中共有8种字符[A,B,C,D,E,F,G,H]，分别出现2次. 1次. 4次. 5次. 7次. 3次. 4次和9次。 1）试构造出哈夫曼编码树，并对每个字符进行编码 2）问该字符串的编码至少有多少位。 A:00000 B:00001 C:100 D:001 E:11 F:0001 G:101 H:01 其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。 四 . 算法设计 A B F D H C G E 1. 设计算法求二叉树的结点个数 2. 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲 3. 编写算法交换二叉树中所有结点的左右子树。 第七章图 一. 填空题 1. 设无向图G中顶点数为n，则图G至少有0 条边，至多有n(n-1)/2条边；若G为有向图，则至少有0 条边，至多有n(n-1)条边。 2. 任何连通图的连通分量只有一个，即是它自身 3. 若一个有向图由邻接矩阵表示，则计算第j个顶点入度的方法是求矩阵第j列元素之和 4. 图的深度优先遍历类似于树的先根遍历，广度优先遍历类似于树的层序遍历。 5. 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为Ｏ(n2)，利用Kruskal算法求最小生成树的时间复杂度为Ｏ(elog2e)。 二. 选择题 1. 在一个无向图中，所有顶点的度数之和等于所有边数的（C）倍。 A 1/2 B 1 C 2 D 4 2. n个顶点的强连通图至少有（A）条边。 A n B n+1 C n-1 D n×(n-1) 3. 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（C）。 A 1 B n/2 C n-1 D n 4. 对于一个具有n个顶点的无向图用邻接矩阵存储，则该矩阵的大小是（D）。 A n B (n-1)2 C n-1 D n2 5. 设无向图G=(V, E)和G' =(V', E' )，如果G' 是G的生成树，则下面的说法中错误的是（B ）。 A G' 为G的子图 B G' 为G的连通分量 C G' 为G的极小连通子图且V= V' D G' 是G的一个无环子图 6. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（D ）。 A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 7. 下面关于工程计划的AOE网的叙述中，不正确的是（ B ） A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 三. 计算题 1. 已知一个连通图如图所示，试给出图的邻接矩阵和邻接表 存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。 邻接矩阵表示如下： 深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如右： 2. 已知无向图G的邻接表如下图所示，分别写出从顶点1出发的深度遍历和广度遍历序列，并画出相应的生成树。 深度优先遍历序列为：1，2，3，4，5，6 对应的生成树为： 广度优先遍历序列为：1，2，4，3，5，6 对应的生成树为： 3. 下图所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 4. 如右图所示的有向网图，利用Dijkstra算法求从顶点v1到 其他各顶点的最短路径。 从源点v1到其他各顶点的最短路径如下表所示。 源点终点最短路径最短路径长度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 5. 已知一个AOV网如下图所示，写出所有拓扑序列。 拓扑序列为：v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。 四. 算法设计 1. 设计算法，将一个无向图的邻接表转换成邻接矩阵。 第1章绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据 类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={ 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 数据结构考试题库 绪论 一、填空题 1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。 2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。 3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。 4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。 5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。 ？6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。 7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。 二、选择题 1.数据的不可分割的基本单位是(D)。 A.元素 B.结点 C.数据类型 D.数据项 *2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。 A.正确 B.不正确 C.不确定 D.无法选择 3.线性结构是指数据元素之间存在一种(D)。 精心整理，用心做精品2 A.一对多关系 B.多对多关系 C.多对一关系 D.一对一关系 4.在数据结构中，从逻辑上可以把数据结构分成(A)。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 5.线性表若采用链式存储结构时，要求内存中可用存储单元的 地址( D)。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以 三、简答题 1.算法的特性是什么。 答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构 一、填空题 1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。 2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。 3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。 4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。 5.从一个栈删除元素时，首先取出(栈顶元素)，然后再使(栈顶指针)减1。 6.子串的定位操作通常称做串的(模式匹配)。 精心整理，用心做精品3 一．是非题 （正确的打“√”，错误的打“×”。） 1. 数据结构可用三元式表示（D，S，P）。其中：D是数据对象，S是D上的关系， P是对D的基本操作集。× 2. 线性表的链式存储结构具有可直接存取表中任一元素的优点。× 3. 字符串是数据对象特定的线性表。 4. 二叉树是一棵结点的度最大为二的树。× 5．邻接多重表可以用以表示无向图，也可用以表示有向图。× 6．可从任意有向图中得到关于所有顶点的拓扑次序。× 7．一棵无向连通图的生成树是其极大的连通子图。× 8．二叉排序树的查找长度至多为log2ｎ。× 9．对于一棵m阶的B-树.树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有┌m/2┐个关键字。× 10．对于目前所知的排序方法，快速排序具有最好的平均性能。 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。× 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。× 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。× 18. 平均查找长度与记录的查找概率有关。 19. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。× 20. 算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。× 二．选择题 1. 若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到 ( e ) 的序列。 a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1 2. 递归程序可借助于( b )转化为非递归程序。 a:线性表 b: 栈 c:队列 d:数组 3. 在下列数据结构中( c )具有先进先出（FIFO）特性， ( b )具有先进后出(FILO）特性。 a:线性表 b:栈 c:队列 d:广义表 4. 对字符串s=’data-structure’ 执行操作replace(s,substring(s,6,8),’bas’) 第1章概论 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①Ｃ、数据信息在计算机中的②A以及一组相关的运算等的课程。 ①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 计算机算法指的是① C ，它必具备输入、输出和② B 等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 3.下面程序段的时间复杂度是D for(i=0;i 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构期末考试试题及答案 、选择题 评价一个算法时间性能的主要标准是()。1. A、算法易于调试 B、算法易于理解 C、算法的稳定性和正确性 D、算法的时间复杂度 )等五个特性。计算机算法具备有输入、输出、 2. A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、XX、稳定性和XX 。带头结点的单链表head为空的判定条件是()3. A、h ead==NULL B、h ead->next==NULL C、head->next==head D、head！=NULL 以下关于线性表的说法不正确的是()。4. A、线性表中的数据元素可以是数字、字符、记录等不同类型。 B、线性表中包含的数据元素个数不是任意的。 C、线性表中的每个结点都有且只有一个直接前趋和直接后继。 D、存在这 样的线性表：表中各结点都没有直接前趋和直接后继。 在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。 5.A、基地址 B、结点大小 C、向量大小 D、基地址和结点大小 ()运算中，使用顺序表比链表好。6. A、插入 B、删除 C、根据序号查找 D、根据元素值查找一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动()个元素7.A、n-i B、n-i+1 C、n-i-1 D、i ()适合作为经常在首尾两端操作线性表的存储结构。8. A、顺序表 B、单链表 C、循环链表 D、双向链表 栈和队列的共同点是() 9. A、都是先进后出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点 一个队列的入列序列是1234，则队列的输出序列是()。10. A 、4321 B 、12 3 4 C 、1432 D 、 3241队列与一般的线性表的区别在于()。11. A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同 假上溢”现象会出现在()中。12. A、循环队列 B、队列 C、链队列 、顺序队列D.二、填空 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法 ② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 数据结构考试及答案（） 作者: 日期: 2 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D） A 必须是连续的B部分地址必须是连续的 C 一定是不连续的D可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 （D ）。 An B n/2 C （n-1）/2 D （n+1）/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（D ）o A s—link = p—link ；p—link = s； B p—link = s; s—link = q; C p—link = s—link ；s—link = p； D q—link = s; s—link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（C ）方法最好。 A 起泡排序 B 堆排序C锦标赛排序 D 快速 排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（B ）o A 求子串B模式匹配C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j] 占用3个存储字，行下标i从1到8, 列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈B队列C循环队列D优先队列 9、一个队列的进队列顺序是1,2, 3, 4 ，则出队列顺序为（C ）。 10、在循环队列中用数组A[0.. m-1]存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A （ front - rear + 1） % m B （rear - front + 1） %m C （ front - rear + m） % m D （ rear - front + n） % m 11、一个数组元素a[i]与（A ）的表示等价。 A * （a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数 A指针 B 引用C值 D 变量 13、下面程序段的时间复杂度为（C) for (i nt i=0;i 第1章概论 1.数据、数据元素、数据结构、数据类型的含义分别是什么？ 数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。 数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。 数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。 数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。 2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？ 逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息： ①数据元素的信息； ②各数据元素之间的关系。 物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。 数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。 3.数据结构的主要操作包括哪些？ 对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： ●创建：建立一个数据结构； ●清除：清除一个数据结构； ●插入：在数据结构中增加新的结点； ●删除：把指定的结点从数据结构中删除； ●访问：对数据结构中的结点进行访问； ●更新：改变指定结点的值或改变指定的某些结点之间的关系； ●查找：在数据结构中查找满足一定条件的结点； ●排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。 4.什么是抽象数据类型？如何定义抽象数据类型？ 抽象数据类型（Abstract Data Type 简称ADT）是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。 对抽象数据类型的描述一般用（D,R,P)三元组表示，抽象数据类型的定义格式为： ADT<抽象数据类型名> { 数据对象D：<数据对象的定义> 数据关系R：<数据关系的定义> 基本操作P：<基本操作的定义> 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（ A ）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的_ _尾______进行，删除操作是在队列的____ 首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。严蔚敏版数据结构课后习题答案-完整版
数据结构试题库答案
2017年数据结构期末考试题及答案A
数据结构习题及参考答案
《数据结构》题库及答案
数据结构考试题库
数据结构试题(含答案)
数据结构 习题答案
数据结构试题及答案(10套最新)
数据结构期末考试试题及答案
数据结构考试题库含答案
数据结构习题及答案——严蔚敏
算法与数据结构题库与答案
《数据结构》期末考试题及答案
数据结构试题及答案
数据结构习题与答案
数据结构考试及答案()
数据结构习题参考答案
数据结构试题及答案(10套最新)
相关主题
文本预览