下载文档原格式
习题集一、填空题⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。
⑹ 算法的描述方法通常有（）、（）和（）三种，⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。
⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*logn，则表示成数量级的形式为（）。
(9)顺序存储结构的特点是（），链接存储结构的特点是（）。
(10) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。
(11) 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。
(12) 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。
(13) 单链表中设置头结点的作用是（）。
(14) 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。
(15)在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。
(16) 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
（17）已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。
A 108B 180C 176D 112（18）在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。
A O(0)B O(1)C O(n)D O(n2)（19）在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。
“数据结构”期末考试试题一、单选题(每小题2分，共12分)1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。
A． HL＝ps p一>next＝HLB． p一>next＝HL；HL＝p3C． p一>next＝Hl；p＝HL；D． p一>next＝HL一>next;HL一>next＝p；2．n个顶点的强连通图中至少含有( )。
A.n—l条有向边B.n条有向边C.n(n—1)／2条有向边D.n(n一1)条有向边3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。
A.O(1)B.O(n)C.O(1Ogzn)D.O(n2)4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。
A．24 B．48C． 72 D． 535．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。
A.整形B.引用型C.指针型D.常值引用型·6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。
A．O(n) B．O(1)C．O(n2) D．O(10g2n)二、填空题(每空1分，共28分)1．数据的存储结构被分为——、——、——和——四种。
2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。
3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。
4．在一棵高度为h的3叉树中，最多含有——结点。
5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。
7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。
顺序表实验报告一、实验内容和目的实验目的：掌握顺序表的建立、查找、插入和删除操作。
掌握有序表的建立、合并、插入操作。
实验内容：1. 顺序表的建立2. 顺序表的遍历3. 顺序表的元素查找4. 顺序表的元素插入5. 顺序表的元素删除6. 有序表的建立7. 有序表的遍历8. 有序表的元素插入9. 有序表的合并二、实验原理基本原理：通过连续的地址空间实现逻辑上和物理上连续的储存的一系列元素。
并在此基础上进行元素的添加，查找，删除操作。
有序表的插入算法：元素插入之前的，先跟有序表中的逐个元素进行对比，以找到合适的插入位置。
例如，已有有序表L，要向L 中插入元素18L={13,15,17,19,20,35,40}第一步：将18与L1进行比较，18 > L1，不是合适的插入位置。
第二步：将18与L2进行比较，18>L2，仍然不是不是的插入位置。
重复上述步骤，知道找到18≤Ln，然后在(n-1) 和n之间插入元素。
（如果元素比有序表中的所有元素都要大，则把该元素放到有序表的最后）此例子中，L n-1 = 17，L n = 19插入元素之后的有序表L为：L′={13,15,17,18,19,20,35,40}仍然保持有序。
重置光标的位置：程序接受两种方式的输入。
一种是输入数字后按回车，一种是利用空格间隔的连续几个数字。
然而，在使用后者输入数字的时候，会出现提示输出不正确的问题。
（如图）这个问题的原因简单如下：当程序输出“请输入第2个数字：”的时候，应该等待用户输入；然而，在程序等待输入第一个数字的时候，用户输入了五个数字。
因此，程序输出“输入第2个提示以后”，程序发现仍然有数据没有进行处理，因此把上次输入但未处理的字符当成是用户的输入。
所以没让用户输入数据就自动继续执行。
解决这个问题的思路：每次输出提示时，将光标移动到行首，因此，输出提示的时候会自动覆盖已经输出的提示信息。
效果如下：具体的解决方法：#include<windows.h>// 将光标移动到行首void ResetCursor(){HANDLE hOut;COORD cTarget;CONSOLE_SCREEN_BUFFER_INFO info;int y = 0;hOut = GetStdHandle(STD_OUTPUT_HANDLE);GetConsoleScreenBufferInfo(hOut, &info);y = info.dwCursorPosition.Y;cTarget.X = 0;cTarget.Y = y;SetConsoleCursorPosition(hOut, cTarget);}三、程序流程图四、实现步骤4.1 创建顺序表的实现①通过scanf 函数从键盘中读入数据，并通过scanf函数的返回值判断用户输入的是数字还是非数字，作为判断输入结束的判断。
第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。
【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。
【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。
【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。
【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。
⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。
【解答】p->next=head【分析】如图2-8所示。
⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。
【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。
【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。
⑻可由一个尾指针唯一确定的链表有（）、（）、（）。
【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。
实验报告课程数据结构及算法实验项目 1.顺序表的建立和基本运算成绩专业班级*** 指导教师***姓名*** 学号*** 实验日期***实验一顺序表的建立和基本运算一、实验目的1、掌握顺序表存储结构的定义及C/C++语言实现2、掌握顺序表的各种基本操作及C/C++语言实现3、设计并实现有序表的遍历、插入、删除等常规算法二、实验环境PC微机，Windows，DOS，Turbo C或者Visual C++三、实验内容1、顺序表的建立和基本运算（1）问题描述顺序表时常进行的运算包括：创建顺序表、销毁顺序表、求顺序表的长度、在顺序表中查找某个数据元素、在某个位置插入一个新数据元素、在顺序表中删除某个数据元素等操作。
试编程实现顺序表的这些基本运算。
（2）基本要求实现顺序表的每一个运算要求用一个函数实现。
（3）算法描述参见教材算法2.3、算法2.4、算法2.5等顺序表的常规算法。
（4）算法实现#include<malloc.h> // malloc()等#include<stdio.h> // NULL, printf()等#include<process.h> // exit()// 函数结果状态代码#define OVERFLOW -2#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等typedef int Boolean; // Boolean是布尔类型,其值是TRUE或者FALSE//-------- 线性表的动态分配顺序存储结构-----------#define LIST_INIT_SIZE 10 // 线性表存储空间的初始分配量#define LIST_INCREMENT 2 // 线性表存储空间的分配增量typedef int ElemType;struct SqList{ElemType *elem; // 存储空间基址int length; // 当前长度int listsize; // 当前分配的存储容量(以sizeof(int)为单位)};void InitList(SqList &L) // 算法2.3{ // 操作结果：构造一个空的顺序线性表LL.elem=new ElemType[LIST_INIT_SIZE];if(!L.elem)exit(OVERFLOW); // 存储分配失败L.length=0; // 空表长度为0L.listsize=LIST_INIT_SIZE; // 初始存储容量}void DestroyList(SqList &L){ // 初始条件：顺序线性表L已存在。
杭州电子科技大学学生考试卷〔A〕卷一．是非题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)7 对于插入、删除而言，线性表的链式存储优于顺序存储。
(t)8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
(f)9. 栈和队列是操作上受限制的线性表。
(t)10. 队列是与线性表完全不同的一种数据结构。
(f)11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。
(f)12. 栈和队列也是线性表。
如果需要，可对它们中的任一元素进行操作。
(f)13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。
(f)14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。
(f)15 二叉树是一棵结点的度最大为二的树。
(f)16 赫夫曼树中结点个数一定是奇数。
(t)17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。
(t)18 假设B是一棵树，B′是对应的二叉树。
则B的后根遍历相当于B′的后序遍历。
(f)19. 通常，二叉树的第i层上有2i-1个结点。
(f)20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。
(t)21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。
(t)22 由树结点的先根序列和后根序列可以唯一地确定一棵树。
实验一、有序表的建立、插入与删除
一、实验目的
１、了解有序表的顺序存贮结构。
２、掌握有序表元素在内存中是怎样存贮的。
３、在有序表中实现如下操作：
(1)插入一个新元素到第i个位置。
使原来标号为增1。
(2)删除第i个位置的元素。
(3)存一个新元素到第i个位置。
(4)读表
(5)检索表中第i个元素。
(6)寻表的长度
二、实验原理
（一）线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。
例如26个英文元素的字母表：（A，B，C，D，···）。
其数据结构的描述为：
Linear_list=(D,R)其中：D={a i|a i属于D0,i=1,2,3,···}R={N},N={<a i-1,a i>|i=2,3,4,···}。
本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：
LOC(a i+1)=LOC(a i)+m。
其中m是存放每个元素所占的内存字数。
LOC(a i)=LO+m·(i-1)。
其中LO是a i的地址，即首地址。
（二）实验程序说明
插入一个新元素到第i个位置，既把元素a i向后移一个位置，成为元素a i+1，把新元素放入到第i个位置，其他元素依次后移。
存一新元素到第i个位置是把元素a i冲掉后存上新值。
删除第i个元素就是把余后的元素依次向前移一个位置。
即：以元素a i+1，a i+2，···，
依次取代a i，a i+1，···。
删除后的表长是n-1（n是原表长）。
三、程序流程图
四、参考程序
/* 有序表的建立、插入与删除 */
static int array[100];
int j,i,n,p;
int ch;
void du()
{
printf("please tell me which numbers do you operate:");
scanf("%d",&i);
while (i>n)
{
printf("ERROR,please enter new element");
scanf("%d",&i);
}
}
void da()
{
printf("the list is:");
for(j=0;j<n;j++)
printf("%3d",array[j]);
printf("\n");
}
void show()
{
printf("-----------------------------------\n"); printf(" the function of the list\n");
printf(" 1: insert\n");
printf(" 2: delete\n");
printf(" 3: save new element\n");
printf(" 4: read list\n");
printf(" 5: check\n");
printf(" 6: the length of the list\n");
printf(" 0: end\n");
printf("-----------------------------------\n"); }
main()
{
printf("please input the length of list:");
scanf("%d",&n);
printf("\n");
printf("please enter number:");
for (i=0;i<n;i++)
scanf("%d",&array[i]);
p=1;
while (p!=0)
{
show();
printf ("enter p: ");
scanf("%d",&p);
if(p>=0&&p<=6)
{switch(p)
{
case 1:
printf("the inserted number places the front of the operation\n");
du();
for (j=n-1;j>=i-1;j--)
array[j+1]=array[j];
printf("please enter number:\n");
scanf("%d",&ch);
array[i-1]=ch;
n+=1;
da();
break;
case 2:
du();
for(j=i-1;j<=n;j++)
array[j]=array[j+1];
n-=1;
da();
break;
case 3:
du();
printf("please enter new number:\n");
scanf("%d",&ch);
printf("\n");
array[i-1]=ch;
da();
break;
case 4:
da();
break;
case 5:
du();
printf("what is the %d number:",i);
printf("%3d\n",array[i-1]);
break;
case 6:
printf("the length of the list is:");
printf("%3d\n",n);
break;
case 0: p=0; break;
}
}
}
printf("ERROR,please enter new number\n"); }。
