当前位置:文档之家› 大学 数据结构考试题和答案

大学 数据结构考试题和答案

第1章绪论《》1、填空题1.常见的数据结构有_线性__结构,__树形___结构,__图形__结构等三种。

2.常见的存储结构有__顺序存储_______结构,__链式存储____结构等两种。

3.数据的基本单位是_数据元素___,它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系,常见的结构可分为两大类,__线性结构____和__非线性结构___。

2、应用题1、给出以下算法的时间复杂度.void fun(int n){int i=1,k=100;while(i<n){k=k+1;i=i+2;}}时间复杂度为____O(n)_____。

2、给出以下算法的时间复杂度.void fun2(int n){int i=1,k=100;while(i<n){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-12.在单链表中,如果在结点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-13、判断题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){//寻找到插入点位置,插入sq->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 // 假定表空间大小为100struct 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; //插入xL.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:"<<endl;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+80B. A+76C.A+82D.以上都不对2.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为( D );Head(Tail(Head(Tail(Tail(A)))))A.(g) B.(d) C.c D.d3、判断题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 ⌋-12.设二叉树的树根为第一层,则第i层上至多有__C_____结点。

(A)1 (B)2 (C)2i-1 (D)2i-13、判断题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=244a b2. 设一棵二叉树的先序遍历序列为abcde,中序遍历序列为badce,请画出对应的二叉树,并写出对应后序遍历序列。

相关主题