第1章绪论《》
1、填空题
1.常见的数据结构有_线性__结构，__树形___结构，__图形__结构等三种。
2.常见的存储结构有__顺序存储_______结构，__链式存储____结构等两种。
3.数据的基本单位是_数据元素___，它在计算机中是作为一个整体来处理的。
4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，__线性结构____和__非线性结构___。
2、应用题
1、给出以下算法的时间复杂度.
void fun(int n)
{
int i=1,k=100;
while(i { k=k+1; i=i+2; } } 时间复杂度为____O（n）_____。 2、给出以下算法的时间复杂度. void fun2(int n) { int i=1,k=100; while(i { i=i*10; k=k+1; } } 时间复杂度为____O（log n）___________。 第2章线性表 1、填空题 1. 线性表按照存储结构不同主要有两种实现方式，一种是__顺序_表，另一种是___链___表。 2.顺序表采用__随机___访问机制对数据元素进行访问。 3.若在单链表结点p的后面插入一个新的结点s，则其操作序列为: ①____s->next=p->next_____________； ②____p->next=s___________________； 4.在单向链表中，若要删除某个结点p，一般要找到__p的前趋__结点，才能实现该操作。 2、选择题 1.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A。 (A)n (B)2n－1 (C)2n (D)n-1 2.在单链表中，如果在结点p之后插入一个新结点s，其操作为 A 。 （A）s->next=p->next; p->next=s; （B）p->next=s; s->next=p->next; （C）s->next=p; p->next=s->next; （D）p->next=s; s->next=p; 3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为( C )。(1≤i≤n) A．O(0) B．O(1) C.O(n) D．O(n2) 4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为( B )。(1≤i≤n+1) A．n-i B．n-i+1 C. i D．n-i-1 3、判断题 1.线性表中每一个元素都有一个前驱和一个后继。（×） 4、程序设计题 1、单链表的结点结构定义如下： struct LinkNode { LinkNode *next; int data; }; 请根据述函数的功能写程序。 void Insert(LinkNode *h,LinkNode *s) {//h指向链表的头结点（即使链表中没有元素，头结点也存在。） //链表中元素已经递增有序 //函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序 LinkNode *p,*q;//q指向p的前驱 q=h; p=h->next; while(p) { if(p->data>s->data) {//寻找到插入点位置，插入s q->next=s; s->next=p; return; } else { q=p; (1分) p=p->next; (1分) } } //当表中没有比s大的结点时，插入到表尾 s->next=q->next; (2分) q->next=s; (2分) } 2、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。顺序表的结构定义如下： #define ListSize 100 // 假定表空间大小为100 struct SqList { int elem[ListSize]; // 数组elem用于存放表中的数据 int length; // 当前的表长度 }; //以上为顺序表的结构 //函数头定义如下 void InsertIncreaseList( SqList &L ,int x ) { int i; if ( L.length>=ListSize) cout<<”OVERFLOW”;//判断是否溢出 for ( i=L.length ; i>0 && L.elem[ i-1 ] > x ; i--) L.elem[ i ]=L.elem[ i-1 ] ; // 比较并移动元素 L.elem[ i ] =x; //插入x L.length++; //表长增1 } /////// 3、单链表中结点的结构如下所示： typedef struct node { int data; struct node *next; }node; 请设计满足下述功能的函数。 要求：建立带头结点的单链表H，要求函数从屏幕上读入m个整数，每读入一个，便生成相应的结点，并且把它插入到链表H的尾部。函数形式为void CreateLinkList(node *H)。 参考程序： void CreateList(node *H) {//H指向头指针 int m,temp; cout<<"输入数据的个数："; cin>>m;// int i=1; node *tail; H->next=NULL; tail=H; while(i<=m) { cout<<"please input your number:"< cin>>temp; node *t=new node ; t->data=temp; t->next=tail->next; tail->next=t; tail=t; i++; } 第3章栈和队列 1、填空题 1.栈和队列在本质上都是___线性表__________。 2.栈的操作特点是__后进先出_。队列的操作特点是_先进先出__。 2、选择题 1.消除递归不一定需要使用栈，此说法___A____。 A. 正确 B. 错误 2.对于栈，输入序列为（1，2，3，4），不可能得到的输出序列有__D_____。 (A)（1，2，3，4）(B)（4，3，2，1） (C)（1，3，4，2）(D)（3，1，2，4） 3.用单循环链表表示队列，正确的说法是B。 (A)可设一个头指针使入队、出队都方便； (B)可设一个尾指针使入队、出队都方便； (C)必须设头尾指针才能使入队、出队都方便； (D)无论如何,只可能使入队方便。 3、判断题 1.栈的特点是先进先出。（×） 2.可以在队列的任意位置插入元素。（×） 3.递归程序化非递归程序必须用到栈。（×） 4.如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（√） 5.在用顺序表表示的循环队列中，可用标志位来区分队空或队满的条件。（√） 第4章串 1、选择题 1. 设有两个串p和q，求q在p中首次出现的位置的运算称作（B） A．连接 B．模式匹配 C．求子串 D．求串长 2、判断题 1.空串和空格串是同一个概念，二者没有区别。（×） 第5章数组和广义表 1、填空题 1.二维数组在内存中存储可以有两种存储方式，一种是___行__优先存储，一种是列 优先存储。 2.设广义表L＝(（），（），（（））)。则head(L)是（）； tail(L)是(（），（（））) ；L的长度是3；L的深度是 3 。 3.设广义表L＝(（a），（b），（（c））) 则head(L)是__（a）__； tail(L)是_(（b），（（c））)___。 2、选择题 1.在C语言中，如果有数组定义 int A[8][9]；假定每个整型数据占2字节，则数 组元素A[4][4]的地址是（A）。 A. A+80 B. A+76 C.A+82 D.以上都不对 2.广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为( D )； Head(Tail(Head(Tail(Tail(A))))) A．（g） B.(d) C.c D.d 3、判断题 1.在C语言中，多维数组的存储采取的是行优先的方式。（√） 2.广义表在本质上也是线性表。（×） 3.可以用三元组存储法来压缩存储稀疏矩阵。（√） 4.已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。 ( √ ) 第6章树和二叉树 1、填空题 1.一棵62个叶结点的完全二叉树,最多有___62*2=124______个结点。 2.若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有- ____2^h-1___________个结点，最少有___2^(h-1)______个结点。 3.设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为-____2^(k+1)-1____________，最小结点数为____k+1____________。 4.设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为-_______2^k-1_________，最小结点数为____k______。 2、选择题 1.具有N个结点的完全二叉树的深度是__B______。 (A)? log2N ?(B)? log2N ?+1 (C)? log2(N) ?(D)? log2N ?-1 2.设二叉树的树根为第一层，则第i层上至多有__C_____结点。 (A)1 (B)2 (C)2i-1 (D)2i-1 3、判断题 1.二叉树的左右子树次序是严格的，不能够任意改变。（√） 2.若根为第一层，则深度为k的满二叉树的结点为2^k-1 。 （√） 3.二叉树的三叉链表存储结构可以方便的访问到双亲结点。（√） 4、应用题 1.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题： （1）什么是哈夫曼树？（3分） （2）根据题目所给频率值，画出相应的哈夫曼树。（11分） （3）给出各个字符对应的哈夫曼编码。（6分） （4）该段文字经过哈夫曼编码后，长度是多少。（4分） 参考答案如下： （1）答案为：带权路径长度最小的二叉树称为哈夫曼树。（3分） （2）根据题目所给频率值，画出相应的哈夫曼树。（11分，每个结点1分） （3）给出各个字符对应的哈夫曼编码。（6分） a:1110 b:1111 c:110 d:00 e:01 f:10 （4）该段文字经过哈夫曼编码后，长度是多少。（4分） (7+9)*4+12*3+(22+23+27)*2=244 或者100+45+55+28+16=244 a b 2. 设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。（15分） 参考答案如下： (1)画出二叉树（10分） 错一个结点扣2分。 （2）后序遍历序列为：bdeca （5分） 3. 通信报文中出现的字符A 、B 、C 、D 、E ，在报文中出现的频率分别为0.23、0.2、 0.32、0.12、0.13，分别给出相应字符的哈夫曼编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共14分） 参考答案如下： 为处理方便，关键字都乘以100，为{23，20，32，12，13} 构造哈夫曼树为：（9分,每个结点1分） 所以编码为：A ：01 B ：00 C ：11 D ：100 E ：101 （5分，每个编码1分） 4. 某二叉树结点的中序序列为H ，B ，C ，D ，E ，F ，G ，后序序列为B ，D ，C ，H ，F ， G ，E ，请据此画出该二叉树，再给该树加上中序线索。（共15分） 对应的二叉树为：（7分,每个结点1分）对应中序线索树为：（8分，每条线索1分） 5 5.请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。（10分） 证明：令树中结点总数为N，度为1的结点个数为n1。 则树中结点数满足下列公式：n0+n1+n2=N 从度的角度来考虑，满足下列公式：2n2+n1+1=N 从而得证：n0=n2+1 5.请按照孩子-兄弟表示法，将图1所示树转化为二叉树。（共14分） 解：（每个结点2分） 6.设二叉树如图2 历、后序遍历序列。（共15分） 8. （1）写出如图所示二叉树的中序遍历结果。（8分）（2）画出二叉树的中序后继线索。（10分） （1）中序遍历结果：ADBCHFEG ——共8 （2）二叉树的中序后继线索如图 ——共10分，每个后继线索2分 9. 已知某二叉树的前序遍历序列为：A B C D E F G 和中序遍历序列为：C B E D A F G 。请画出该二叉树。 答案如下： 10. 已知通信联络中只可能出现A 、B 、C 、D 、E 、F 、G 、H 共8种字符，其出现次数分别为 5，28，7，9，14，23，3，11次。 （1）请画出赫夫曼树（权值小的结点在左边）。（15分） （2）计算该树的带权路径长度。（3分） 答案：此答案错误！！！ （1）赫夫曼树构造如下。树中结点位置正确者，每个1分，共15分。 （2）该树的带权路径长度为 （5+3+7+8）*4+（11+14）*3+（23+29）*2=271 ————3分 5、读程序写结果 已知二叉树的结点结构如下： struct Node { int data; Node *lchild,*rchild; }; 某棵二叉树的形态如右图： 根据要求解答下题： 1、 (共5分) int fun1(Node *root) { if(root==0) return 0; int l,r; l=fun1(root->lchild); r=fun1(root->rchild); if(l>=r) return l+1; else return r+1; } （1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分) 函数fun1的返回值是3。 （2）函数fun1的功能是什么？(3分) 函数fun1的功能是求二叉树的高度。 2、 (共6分) int fun2(Node *root) { if(root==0) return 0; int l=fun2(root->lchild ); int r=fun2(root->rchild ); return l+r+1; } （1）当root是指向结点A的指针时，函数fun1的返回值是多少？(2分) 函数fun1的返回值是5。 （2）函数fun1的功能是什么？(4分) 函数fun1的功能是求二叉树中所有结点的个数 第7章图 1、填空题 1. 有n个顶点的有向连通图最多有 n(n-1) 条边，最少有 n-1 条边。 2.具有n个顶点的完全无向图有__2/n(n-1)______条边，完全有向图有______n(n-1)__条边。 2、选择题 1. _____b_____方法可以判断出一个有向图中是否有环（回路）。 (A)深度优先遍历 (B)拓扑排序 (C)求最短路径 (D)求关键路径 2.关键路径是指__b________。 (A)从开始事件到终止事件路径长度最短的路径 (B)从开始事件到终止事件路径长度最长的路径 (C)从开始事件到终止事件活动最少的路径 (D)从开始事件到终止事件活动最多的路径 7.方法 b 可以判断出一个有向图中是否有环（回路）。 (A)深度优先遍历 (B)拓扑排序 (C)求最短路径 (D)求关键路径 3、判断题 1.具有n个顶点的有向图最多有n*(n-1)条边。（t ） 2.在AOV-网中，不应该出现有向环，因为存在环就意味着活动可以以自己为先决条件。（ t ） 4、应用题 1、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。(11分) A B C D E F G H I J K 答案为：ABGCHDIEJFK (对一个1分) 2. 请给出图1的所有最小生成树。（10分） 共两棵。 第一棵为：(5分)错一条边扣1分。 第二棵为：(5分)错一条边扣1分。 3. 请给出图2的所有拓扑排序序列。 （16） 答案如下：仅有两个 第一个：abcdefgh (错一个字符扣1分) 第二个：abcdegfh (错一个字符扣1分) 4、对于有向无环图（如图2），写出它的所有不同的拓扑有序序列。(共16分) 图1 序列为：1、3、2、4、 5、6、7、8 6. 已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分） 1 2 3 4 5 6 图2 (1) 请画出该图。（6分） （2）对其从顶点A 开始进行深度优先遍历，写出遍历序列。（6分） （1） 请画出该图。（6分）错一个结点扣1分。 （2）对其从顶点A 开始进行深度优先遍历，写出遍历序列。（6分, 错一个字符扣1分） 序列为：ABDECF 7、（本题总计 7 分） 图2 构造该图的最小生成树。 图的最小生成树如下——每条边1分，共7分 第9章查找 1、选择题 1.若在线性表中采用二分查找法查找元素，该线性表应该( a )。 A．元素按值有序 B．采用顺序存储结构 C．元素按值有序，且采用顺序存储结构 D．元素按值有序，且采用链式存储结构 2.对二叉排序树进行_____b____遍历，可以得到该二叉树所有结点构成的有序序列。 (A) 前序 (B)中序 (C)后序 (D)按层次 3.利用逐点插入法建立序列(51，71，43，81，74，20，34，45，64，30)对应的二叉排序树以后，查找元素34要进行( a )元素间的比较。 A．4次 B．5次 C. 7次 D．10 4.对二叉排序树进行_______b_____遍历，可以得到该二叉树所有结点构成的有序序列。 (A) 前序 (B)中序 (C)后序 (D)按层次 5.散列函数有一个共同性质，即函数值应按( c )取其值域的每一个值。 A.最大概率 B.最小概率 C.同等概率 D.平均概率 6.一个哈希函数被认为是“好的”，如果它满足条件____d_____。 (A)哈希地址分布均匀 (B)保证不产生冲突 (C)所有哈希地址在表长范围内 (D)满足(B)和(C) 7.哈希表的平均查找长度是_______d___的函数。 （A）哈希表的长度（B）表中元素的多少 （C）哈希函数（D）哈希表的装满程度 8.平均查找长度最短的查找方法是__________c__。 （A）折半查找（B）顺序查找（C）哈希查找（4）其他 2、判断题 1.在有序表的查询过程中，设立“哨兵”的作用是为了提高效率。（ t ） 2.对于折半查找，其前提条件是待查找序列只要是有序的即可。（f ） 3、应用题 1. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。 (1)按输入次序构造一棵二叉排序树（只要求画出最终二叉排序树）。 (2)依此二叉排序树，如何得到一个从小到大的有序序列？ 2、若一棵排序二叉树的关键字输入序列为{80，6，10，7，8，25，100，90}，请画出该二叉树。 解：二叉排序树为：（16分，每个结点2分） 3. 已知一组关键字为{1,14,27,29,55,68,10,11,23}，则按哈希函数H(key)=key MOD 13和链地址法处理冲突来构造哈希表。 （1）画出所构造的哈希表。 （2）在记录的查找概率相等的前提下，计算该表查找成功时的平均查找长度。 （1）画出所构造的哈希表。 —— 9个结点，每个1分 0 1 2 3 4 5 6 7 8 9 10 11 12 （2）在记录的查找概率相等的前提下，该表查找成功时的平均查找长度，ASL ＝（1×4＋2×3＋3×2）/9=16/9 —— 2分 4、程序设计题 1.二叉排序树的结点结构如下所示： typedef struct node { int data; struct node *lchild,*rchild; }node； 请编写在二叉排序树T中查找值为x的结点的非递归算法，如果查到，返回指向该结点的指针，否则返回空。函数形式为： node* Search(node *T, int x)。（10分） /////////////// 2.已知整型数组A，从第一个单元（即A[1]）开始存储数据，且一共存储了n个元素。要求编写折半查找元素e的过程。当数组中存在元素e时，返回其下标，否则返回0。（10分） int BinarySearch(int *A,int n,int e) ////////////// 参考程序如下： int BinarySearch(int *A,int n,int e) { int low,high,mid; low=1;high=n; （1分） while(low { mid=(low+high)/2; （2分） if (e ==A[mid]) （1分） return mid; （1分） else if(e high=mid-1; （1分） else low=mid+1; （1分） } return 0; （1分） } 3.已知整型数组A[101]，其中从A[1]到A[100]存储了100个整数，试编写函数int Find(int A[101],int x)，功能为从数组A中折半查找元素x，如果找到则返回x所对应的下标，否则的话返回0。 第10章内部排序 1、填空题 1.快速排序和堆排序的平均时间复杂度分别为____o(nlog2n)-o(n2)____和_ o(nlog2n)_______。 2、选择题 1.下面给出的四种排序法中( d )排序法是不稳定性排序法。 A．插入 B．冒泡 C．二路归并 D．堆排序 2.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其 放在已排序序列的合适位置，该排序方法称为 d 排序法。 (A)插入 (B)选择 (C)希尔 (D)二路归并 3.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其 放在已排序序列的合适位置，该排序方法称为_____a_排序法。 (A)插入 (B)选择 (C)谢尔 (D)二路归并 3、判断题 1.从平均性能而言，快速排序最佳，其所需时间最省。（f ） 4、应用题 1. 对于关键字序列{49，38，65，97，76，13}，回答下述问题。（共12分） （1）写出一趟冒泡排序的结果。（6分） （2）写出一趟快速排序的结果。（6分） 参考答案如下： （1）写出一趟冒泡排序的结果。（6分） {38,49,65,76,13,97} （2）写出一趟快速排序的结果。（6分） {13,38,49,97,76,65} 一、一、单选题（每小题2分，共8分） 1、1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的 平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。 A n B n/2 C (n+1)/2 D (n-1)/2 2、2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间 插入一个s所指的结点,则执行( )。 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; 3、3、栈的插入和删除操作在（）进行。 A 栈顶 B 栈底 C 任意位置 D 指定位置 4、4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的 带权路径长度为（） A 24 B 71 C 48 D 53 二、二、填空题（每空1分，共32分） 1、1、数据的逻辑结构被分为__________、___________ 、________和 ________四种。 2、2、一种抽象数据类型包括______________和_____________两个部分。 3、3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则 该线性表为_________________________________________________。 a 0 1 2 3 4 5 6 7 8 data 4、4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判 断链表为空的条件分别为________________和____________________。 5、5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指 向队首元素的___________，该循环队列的最大长度为__________。 6、6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示； 当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。 7、7、一棵高度为5的二叉树中最少含有_________个结点，最多含有 ________个结点； 一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有 _________个结点。 8、8、在图的邻接表中，每个结点被称为____________，通常它包含三个域： 一是_____________；二是___________；三是_____________。 9、9、在一个索引文件的索引表中，每个索引项包含对应记录的_________ 和___________两项数据。 10、10、假定一棵树的广义表表示为A（B（C，D（E，F，G），H （I，J））），则树中所含的结点数为_________个，树的深度为_________, 树的度为________, 结点H的双亲结点为________,孩子结点为 _______________ 。 11、11、在堆排序的过程中，对任一分支结点进行筛运算的时间复 杂度为_________,整个堆排序过程的时间复杂度为________________。 12、12、在对m阶的B_树插入元素的过程中，每向一个结点插入一 个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索 引项数等于______个，则必须把它分裂为_______个结点。 三、三、运算题（每小题6分，共24分） 1、1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写 出对其进行快速排序的每一次划分结果。 2、2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设 散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 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 .没有共同点 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。 数据结构习题集含答案 目录 选择题 第一章绪论 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; 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 2012年数据结构期末考试题及答案 一、选择题 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．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 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.以顺序方式存储，且数据元素有序 数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 2 分，共 20 分） 1. 栈和队列的共同特点是 （ ）。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 2. 用链接方式存储的队列，在进行插入运算时 （ ）. A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D .头、尾指针可能都要修改 3. 以下数据结构中哪一个是非线性结构？ （ ） A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（io ）, A[2][2]存放 若有18个元素的有序表存放在一维数组 A[19]中，第一个元素放A[1]中, 现进行二分查找，则查找 A [3]的比较序列的下标依次为（ A. 1 ， 2， 3 B. 9， 5， 2， 3 C. 9， 5， 3 D. 9， 4， 2， 3 8. 对n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O （1） B. O （n ） C. O （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 7、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。 A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 课程测试试题（卷） ----------------------以下为教师填写-------------------- I、命题院（部）：数学与计算机科学学院 II、课程名称：数据结构 III、测试学期：20 －20 学年度第学期 IV、测试对象：学院专业级班 V、问卷页数（A4）：页 VI、答卷页数（A4）：页 VII、考试方式：闭卷（开卷、闭卷或课程小论文，请填写清楚） VIII、问卷内容：（请老师在出题时安排紧凑，填空题象征性的留出一点空格，学生将所有的答案做在答题纸上的规定位置，并写清楚大题、小题的题号） 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指 向的结点，则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多 可以组成( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 ( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述 序列出发建堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四 种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 _________，在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是 ________________;删除一个结点时，需要执行的操作是 ______________________________（假设栈不空而且无需回收被删除结点）。 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。数据结构复习题(附答案)
数据结构模拟题(开卷)
数据结构复习题附答案
数据结构模拟试题及答案
2017年数据结构期末考试题及答案A
数据结构期末考试试题及答案
《数据结构C》模拟试题
数据结构考试题库含答案
《数据结构》模拟试卷一及答案
2015年数据结构期末考试题及答案
《数据结构》期末考试题及答案
数据结构模拟试卷(含答案)
数据结构练习试题和答案解析
2017数据结构期末考试试题及答案
数据结构复习题及答案
数据结构期末模拟试题05(有答案)
数据结构复习题及答案
相关主题
文本预览