第2章作业参考答案
1. B
2. A，D
3. 1，n/2，(n-1)/2，n，0，0
4.
templete
void SqList
{
ElemType e;
for (int i = 0; i < len / 2; i++)
{
e = elem[i];
elem[i] = elem[len – i -1];
elem[len – i – 1] = e;
}
}
templete
void LinkList
{
if (!head->next) return;
LinkNode
q -> next = NULL;
tail = q;
while (p)
{
q = p;
p = p –> next;
q –> next = head -> next;
head -> next = q;
}
}
8.
void add(LinkList
int pa_len, pb_len, i, j;
pa_len = pa.Length();
pb_len = pb.Length();
i = j = 1;
Monomial pa_e, pb_e;
pa.GetElem(pa_e, 1);
pb.GetElem(pb_e, 1);
while (i <= pa_len && j <= pb_len)
{
if (pa_e.exp < pb_e.exp)
{
i++;
if (i <= pa_len) pa.GetElem(pa_e, i);
}
else if (pa_e.exp > pb_e.exp)
{
pa.Insert(pb_e, i);
i++;
pa_len++;
j++;
if (j <= pb_len) pb.GetElem(pb_e, j);
}
else
{
if (pa_e.coef += pb_e.coef)
{
pa.SetElem(pa_e, i);
i++;
}
else
{
pa.Delete(pa_e, i);
pa_len--;
}
j++;
if (i <= pa_len) pa.GetElem(pa_e, i);
if (j <= pb_len) pb.GetElem(pb_e, j);
}
}
while (j <= pb_len)
{
pb.GetElem(pb_e, j++);
pa.Append(pb_e);
}
}
第3章作业参考答案
1.
1,4,3,5,2)能，IOIIIOOIOO；
(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。
*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, p n，则在输出序列中不可能出现这样的情形：存在着i 2. 借助栈T，删除栈S中元素值为k的元素。 4. //定义双向栈类 template class DSqStack { public: //双向栈类的各成员函数 DSqStack(int m = 100); ~DSqStack(); bool Empty(int i) const; ElemType & Top(int i) const; void Push(const ElemType &e,int i); void Pop(int i); private: //双向栈类的数据成员 ElemType *base; //基地址指针 int top[2]; //栈顶指针 int size; //向量空间大小 }; //构造函数，分配m个结点的顺序空间，构造一个空的双向栈。 template DSqStack { top[0] = -1; top[1] = m; base = new ElemType[m]; size = m; }//DSqStack //析构函数，将栈结构销毁。 template DSqStack { if (base != NULL) delete[] base; }//~SqStack //判栈是否为空，若为空，则返回true，否则返回false。template bool DSqStack {//i的取值为0或1 if (i == 0) return top[0] == -1; else return top[1] == size; }//Empty //取栈顶元素的值。先决条件是栈不空。 template ElemType & DSqStack {//i的取值为0或1 return base[top[i]]; }//Top //入栈，若栈满，则先扩展空间。插入e到栈顶。template void DSqStack if (top[0] == top[1] - 1) { //若栈满，则扩展空间。 ElemType *newbase; newbase = new ElemType[size + 10]; for(int j = 0; j <= top[0]; j++) newbase[j] = base[j]; for(int k = size - 1; k >= top[1]; k--) newbase[k + 10] = base[k]; delete[] base; base = newbase; size += 10; top[1] += 10; } if (i == 0) base[++top[0]] = e; else base[--top[1]] = e; }//Push //出栈，弹出栈顶元素。先决条件是栈非空。 template void DSqStack {//i的取值为0或1 if (i == 0) top[0]--; else top[1]++; }//Pop 5. (1). A, C, D (2). 从左到右读序列，任何时候累计I的个数都应大于等于O的个数。 (3). bool islegal(char *a) { int s = 0, n = strlen(s); for (int i = 0; i < n; i++) { if (a[i] == “I”) s++; else s--; if (s < 0) return false; } return true; } 7. 借助队列q0和q1，将队列Q中的元素重新排列：奇数值元素在前，偶数值元素在后。 8. 类型定义： typedef struct QNode { QElemType data; struct QNode *next; } QNode, * QLink; template class CycLinkQueue { public: //循环链表队列的各成员函数 CycLinkQueue (); //~CycLinkQueue (); //void Clear(); //bool Empty() const; //int Length() const; //ElemType & GetHead() const; //ElemType & GetLast() const; void Append(const ElemType &e); void Remove(); private: QNode < ElemType > *m_rear; //队尾指针 }; (1) //构造函数，构造一个空的循环链队列。 template CycLinkQueue { m_rear = new QNode m_rear->next = m_rear; } (2) //入队 void CycLinkQueue { QNode < ElemType > *p; p = new QNode p->data = e; p->next = m_rear->next; m_rear->next = p; m_rear = p; } (3) //出队。先决条件是队列不空。 template void CycLinkQueue { QNode < ElemType > *p = m_rear->next->next; m_rear->next->next = p->next; if (p == m_rear) m_rear = m_rear->next; //若出队后队列为空，需修改m_rear。 delete p; } 9. template class SqQueue { public: //循环队列的各成员函数 SqQueue(int m = 100); //~SqQueue(); //void Clear(); //bool Empty() const; //int Length() const; //ElemType & GetHead() const; //ElemType & GetLast() const; void Append(const ElemType &e); void Remove(); private: //循环队列类的数据成员 ElemType *m_base; //基地址指针 int m_front; //队头指针 int m_length; //队列长度 int m_size; //向量空间大小 }; //构造函数，分配m个结点的顺序空间，构造一个空的循环队列。template SqQueue { m_front = m_length = 0; m_base = new ElemType[m]; m_size = m; }//SqQueue //入队，插入e到队尾。 template void SqQueue { int j, k; if (m_length == m_size) { //队满，则扩展空间。 ElemType *newbase; newbase = new ElemType[m_size + 10]; for(j = m_front, k = 0; k < m_length; j = (j + 1) % m_size, k++) newbase[k] = m_base[j]; delete[] m_base; m_base = newbase; m_front = 0; m_size += 10; } m_base[(m_front + m_length) % m_size] = e; m_length++; }//Append //出队。先决条件是队列不空。 template void SqQueue { m_front = (m_front + 1) % m_size; m_length--; }//Remove 10. Length(s)的结果为14 sub1的值为”I am a “ Index(s,”a”,4)的结果为6 s的值为”I am a worker” sub3的值为”goodworker” sub3的值为”good worker” 11. (1) 288 (2) 1282 (3) 1180 (4) 1234 12. (1) k=2i+j-3 (2) i=?(k+1)/3?+1，j=i+(k+1)%3-1 (i用前式代入即可) 15. (1) (a, b) (2) ( ) (3) (b) (4) b (5) (d) 16. （略） 高度最小的树：高度是2，它有n-1个叶结点，1个分支结点。 高度最大的树：高度是n ，它有1个叶结点，n-1个分支结点。 5. n 0=1+n 2+2n 3+…+(m-1)n m 6. 树2种： 二叉树5种： 7. (1) 空树，或二叉树中所有结点的lchild 均为空的二叉树 (2) 空树，或二叉树中所有结点的rchild 均为空的二叉树 (3) 空树，或仅有一个结点的二叉树 9. (1) 第i 层有k i-1个结点 (2) ?(i+k-2)/k ? (i>1) (3) k(i-1)+m+1 (4) (i-1)%k ≠0, i+1 (5) h=?log k (n(k-1)+1)? 10. G H F B D A E C J I J H I B E A C K F G D 12. F I C B H A D E G J 13. 树： 二叉树： H C B F I G D K J E A J C B K E F D I H A G 14. 森林： 二叉树： J D H L K C B A G D F E J I H B G A C E K D F L 16. 赫夫曼树： 3C 3 4C 8 11C 6 5C 1 6C 4 25C 2 36C 7 10C 5 赫夫曼编码：C1(5): 0110，C2(25):10，C3(3):0010，C4(6):0111，C5(10):000，C6(11):010，C7(36):11，C8(4):0011 WPL=(3+4+5+6)*4+(10+11)*3+(25+36)*2=257 17. (1) //求二叉树中叶结点的个数 template int BinaryTree if (!T) return 0; if ((!T->lchild)&&(!T->rchild)) return 1; return _CountLeaves(T->lchild)+ _CountLeaves(T->rchild); } (2) //交换二叉树中每个结点的左右孩子 template void BinaryTree { if (T) { BTNode T->lchild=T->rchild; T->rchild=p; _E xchange(T->lchild); _E xchange(T->rchild); } } 2. (1). 邻接矩阵 邻接表 012340123 401110111000100001100101105000110 1 1 5 (2). DFS: V1,V2,V4,V5,V3,V6 (3). BFS: V1,V2,V3,V4,V5,V6 (4). 深度优先生成树 广度优先生成树 V 2 V 1V 3V 4V 5 V 6 V 6 V 1V 2V 4V 5 V 3 3. (1). 012340123 43 ∞∞ 1 3 ∞∞1 ∞ 6 3 ∞6∞∞ 2 3 ∞∞∞∞ 2∞∞5 ∞ ∞ 5 5 6∞∞ 5 56∞ 5 ∞ (2). 4. (1). 顶点 v1 v2 v3 v4 v5 v6 入度 0 1 2 1 1 2 出度 2 2 1 1 1 0 (2). 邻接矩阵 邻接表 逆邻接表 012340123400000110001100001000000005000110 5 十字链表 4 5 (3). 拓扑序列：V1，V2，V3，V4，V5，V6 V1，V2，V3，V5，V4，V6 V1，V2，V4，V3，V5，V6 6. （略） 第六章 2. 10 68 24 5 11 7 3 1 9 3. 6；19。 6. (1). 78 47 3418 35 2390 9 61 (2). 78 47 3418 35 90 9 61 (3). 不同： 78 47 3418 35 90 9 61 23 7. 平衡的二叉排序树 95 90 1223 40 8 32 15 6256 3阶B-树 95 90 12 , 2340 8 32 15 56,62 9. H(K)=K % 11 ASL=(8+2*2)/10=1.2 注意：为了提高查找的效率，插入时应将链表组织成按值递增或递减有序。 10. 2253804567413 0 1 2 3 4 5 6 7 8 9 10 11 ASL=8/7 数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 《数据结构与算法》（c语言版）期末考复习题 一、选择题。 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 国家二级ACCESS机试选择题（数据结构与算法）模拟试卷3 (总分：60.00，做题时间：90分钟) 一、选择题(总题数：30，分数：60.00) 1.在最坏情况下 （分数：2.00） A.快速排序的时间复杂度比冒泡排序的时间复杂度要小 B.快速排序的时间复杂度比希尔排序的时间复杂度要小 C.希尔排序的时间复杂度比直接插入排序的时间复杂度要小√ D.快速排序的时间复杂度与希尔排序的时间复杂度是一样的 解析：解析：按平均时间将排序分为四类：①平方阶(O(n 2 ))排序：各类简单排序，例如直接插入、直接选择和冒泡排序；②线性对数阶(O(n。log2n))排序：如快速排序、堆排序和归并排序；③O(n1+§))排序：§是介于0和1之间的常数。希尔排序便是一种；④线性阶(O(n))排序：本程序中的基数排序，此外还有桶、箱排序。 2.在深度为7的满二叉树中，度为2的结点个数为 （分数：2.00） A.64 B.63 √ C.32 D.31 解析：解析：因为在任意的二叉树中，度为O的结点(即叶子结点)总比度为2的结点的个数多1个，而度为0的结点数n 0 =2 m-1 (其中m为二叉树的深度)。本题的度为0的结点个数n 0 =2 7-1 =2 6 =64。因此，度为2的结点数n 2 =n 0 -1=63。所以选项B正确 3.设栈的顺序存储空间为S(1：m)，初始状态为top=m+1。现经过一系列入栈与退栈运算后，top=20，则当前栈中的元素个数为 （分数：2.00） A.30 B.20 C.m-19 √ D.m-20 TOP指针向上移动一位。当压入第一个元素时，TOP指针指向m+1-1=m；当压入第二个元素时，TOP指针指向 1n+1．2=m．1；…以此类推，当压入第N个元素时，TOP指针指向m+1-N=20；则N=m+1-20=m-19。因此选项C正确。 4.算法空间复杂度的度量方法是 （分数：2.00） A.算法程序的长度 B.算法所处理的数据量 C.执行算法所需要的工作单元 D.执行算法所需要的存储空间√ 解析：解析：算法空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量，因此选项D正确。 5.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5 数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。 哈夫曼树 时间限制: 100 second 内存限制: 100 Kb 描述 构造哈夫曼树（最优二叉树） 输入 输入n个结点每个结点的权值 输出 构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码 输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示 输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码 数据结构C语言版第一 二章习题答案 Document number：BGCG-0857-BTDO-0089-2022 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构（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．栈6．试分析下面各程序段的时间复杂度。 （1）x=90; y=100;? while(y>0) if(x>100) {x=x-10;y--;} else x++; （2）for (i=0; i 数据结构上机考试试题（C++语言版） 考试要求：本次考试共列考核试题4大题，考生可以在所列4个考核试题中任选3个小题（即可能只属于2个大题），作为上机考核试题。 考核原则：所选题目在上机编程调试通过后即为考核通过。监考教师依据学生编程及调试通过与否情况给予考核成绩。 考核成绩评分标准： 所选3个题目全部编写出程序并调试通过：优 所选3个题目全部编写出程序，但只有2个上机调试通过：良 所选3个题目全部编写出程序，但只有1个上机调试通过：及格 所选3个题目全部编写出程序但都没有上机调试通过，或没有编写出全部程序：不及格。考核时间：2小时。 考核试题： 1、建立一个顺序方式存储的线性表，向表中输入若干元素后进行以下操作： （1）向线性表的表头、表尾或合适位置插入元素 （2）对线性表按升序或降序输出 2、建立一个动态链接方式存储的线性表，向表中输入若干元素后进行以下操作： （1）从单链表中查找指定元素 （2）返回单链表中指定序号的结点值 3、建立一个动态链接结构存储的二叉树，向这棵二叉树进行以下操作： （1）按任中序遍历次序输出二叉树中的所有结点 （2）求二叉树的叶子数 4、编写一个对整型数组A[n+1]中的A[1]至A[n]元素进行选择排序的算法，使得首先从待排序区间中选择出一个最大值并同最后一个元素交换，再从待排序区间中选择出一个最小值并同最第一个元素交换，反复进行直到待排序区间中元素的个数不超过1为止。 #include<> #include<> #include"" //初始化线性表 void InitList(LinearList& L, int ms) { =new ElemType[ms]; if(! { cerr<<"Memory allocation failure!"< 国家二级MS Office高级应用机试（数据结构与算法）模拟试卷 8 (总分：56.00，做题时间：90分钟) 一、选择题(总题数：28，分数：56.00) 1.下列结构中属于线性结构链式存储的是 （分数：2.00） A.双向链表√ B.循环队列 C.二叉链表 D.二维数组 解析：解析：数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。数据的存储结构是指数据的逻辑结构在计算机中的表示。双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，它的存储方式是线性结构链式。循环队列、二叉链表和二维数组都是顺序存储结构。 2.下列叙述中错误的是 （分数：2.00） A.循环链表中有一个表头结点 B.循环链表的存储空间是连续的√ C.循环链表实现了空表与非空表运算的统一 D.循环链表的表头指针与循环链表中最后一个结点的指针均指向表头结点 解析：解析：循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的结点是指针指向，它不一定要是连续的存储空间，也可以是断开的空间。 3.度为3的一棵树共有30个结点，其中度为3、1的结点个数分别为3、4。则该树中的叶子结点数为 （分数：2.00） A.14 B.15 √ C.16 D.不可能有这样的树 解析：解析：根据题目可知本树中还有度为2的结点。树的总结点＝(度1*个数＋度2*个数…)＋1，这里我们设度为2的结点数为x，那么30＝3*3＋2*x＋1*4＋1＝2*x＋14，由此可计算出x＝8。树的叶子结点数等于总结点减去所有度不为0的结点，也就是30－3－8－4＝15。 4.在长度为97的顺序有序表中作二分查找，最多需要的比较次数为 （分数：2.00） A.7 √ B.96 C.48 D.6 解析：解析：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。最多比较次数的计算方式：k＝log 2 n。其中n代表长度，k为比较次数。本题中可以计算出k＝7。 5.下列结构中属于非线性结构的是 （分数：2.00） A.二叉链表 B.二维数组√ C.循环队列 《数据结构》 第五版 清华大学自动化系 李宛洲 2004年5月 目录 第一章数据结构--概念与基本类型 (6) 1.1概述 (6) 1.1.1数据结构应用对象 (6) 1.1.2学习数据结构的基础 (7) 1.1.2.1 C语言中的结构体 (7) 1.1.2.2 C语言的指针在数据结构中的关联作用 (8) 1.1.2.3 C语言的共用体(union)数据类型 (12) 1.1.3数据结构定义 (15) 1.2线性表 (17) 1.2.1 顺序表 (18) 1.2.2 链表 (20) 1.2.2.1链表的基本结构及概念 (20) 1.2.2.2单链表设计 (22) 1.2.2.3单链表操作效率 (29) 1.2.2.4双链表设计 (30) 1.2.2.5链表深入学习 (32) 1.2.2.6稀疏矩阵的三元组与十字链表 (36) 1.2.3 堆栈 (41) 1.2.3.1堆栈结构 (41) 1.2.3.2基本操作 (42) 1.2.3.3堆栈与递归 (44) 1.2.3.4递归与分治算法 (45) 1.2.3.5递归与递推 (49) 1.2.3.6栈应用 (52) 1.2.4 队列 (57) 1.2.4.1队列结构 (57) 1.2.3.2队列应用 (59) 1.3非线性数据结构--树 (64) 1.3.1 概念与术语 (64) 1.3.1.1引入非线性数据结构的目的 (64) 1.3.1.2树的定义与术语 (65) 1.3.1.3树的内部节点与叶子节点存储结构问题 (66) 1.3.2 二叉树 (66) 1.3.2.1二叉树基本概念 (66) 1.3.2.2完全二叉树的顺序存储结构 (68) 1.3.2.3二叉树遍历 (69) 1.3.2.4二叉树唯一性问题 (71) #include //void insert(struct Lnode**L,int n, char d) //从功能化分上，这个函数不需要知道现在插入第几个字符//困为你init函数中是先对一个串的字符进行了排序，所以//这里直接插入链表的尾部就行了 void insert(struct Lnode**L, char d) { struct Lnode *t1,*t2; int j=1; t1=(struct Lnode*)malloc(sizeof(struct Lnode)); t1-> data=d; t1-> next=NULL; if(*L==NULL) { *L=t1; return; } t2=*L; while(t2-> next!=NULL) { t2=t2-> next; } t2-> next=t1; /* if(n==1) { t1-> next=t2; *L=t1; } else { while(j 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 2015.3 目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (43) 第7章查找 (54) 第8章排序 (65) 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 2013-03-08 上机实验题 1.构建两个顺序表示的非空线性表LA和LB (数据元素为整型，其值自行确定)； 2.从线性表LA中删除第i 个元素； 3.将元素e插入到线性表LB中的第i个元素之后； 4.假设LA中不含重复的元素 (LB同)，将线性表LA和LB合并，并输出结果，要求结 果中不含重复的元素。 //构建两个顺序表（定义、初始化） //在一个顺序表中删除指定位置的元素 //在一个顺序表中指定位置插入一个新元素 //将两个线性表LA和LB进行合并 //遍历LB, 如果其中的数据元素不在LA中，则将其插入LA，否则不予处理 //打印线性表LA #define List_Init_Size 100 #define LISTINCREMENT 10 typedef int Status; typedef struct { int * elem; int length; // 当前长度 int ListSize; // 当前分配的存储容量 }SqList; Status Initialize_table (SqList &L) {// 初始化线性表 int i, m, data; L.elem=(int *)malloc(List_Init_Size *sizeof(int)); if (!L.elem) { // 为线性表分配空间 printf("Overflow"); return FAILURE; } L.ListSize=List_Init_Size; L.length=0; printf ("Please input the size of linear table (<=%d): "+ List_Init_Size); scanf_s("%d",&m); for (i=0;i 第1章绪论 5．选择题：CCBDCA 6．试分析下面各程序段的时间复杂度。 （1）O（1） （2）O（m*n） （3）O（n2） （4）O（log3n） （5）因为x++共执行了n-1+n-2+……＋1= n(n-1)/2，所以执行时间为O（n2） （6）O(n) 第2章线性表 1．选择题 babadbcabdcddac 2．算法设计题 （6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; （7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } } （10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 [题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。 void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i 数据结构上机题目 第二次:sqlist-顺序表 2.11 设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。 2.21 试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a1,a2,…,an)逆置为(an,an-1,…,a1)。 第三次:LinkList-单链表 2.15已知指针ha和hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试写一算法将这两个链表连接在一起(即令其中一个表的首元结点连在另一个表的最后一个结点之后)，假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。请分析你的算法的时间复杂度。 2.19已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意，mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。 第四次:cdLinkList-循环链表 2.33已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其他字符），试编写算法将该线性表分割为 三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。 2.38设有一个双向循环链表，每个结点中除有prior，data和next 三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE(L,x)的操作后，被访问的结点（即元素值等于x的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的LOCATE操作的算法。 第五次:outqueue-实验1线性表 实验目的 熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点熟悉链表的各种操作。 时间要求：4学时 问题描述： 约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 基本要求: 利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。 严蔚敏 数据结构C 语言版答案详解 第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、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值 的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。在主函数中输入2个整数、调用函数fun、输出结果。 #include 数fun、输出结果。 #define N 10 #include 1.编写程序，从键盘输入两个整数a和b，计算出a除以b的商和余数。输出时，商数要求保留2位小数，并对第三位进行四舍五入。 (不要求判断b是否0) 方法一： #include 数据结构(c语言版)复习资料
数据结构(c语言版)期末考试复习试题
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷3
数据结构(C语言版)期末复习
数据结构上机例题及答案
经典数据结构上机题_答案解析
数据结构上机考试题
数据结构C语言版第一二章习题答案
数据结构上机考试试题
国家二级MS+Office高级应用机试(数据结构与算法)模拟试卷8
《数据结构》c语言版
数据结构上机题
数据结构C语言版(第2版)严蔚敏人民邮电出版社课后习题答案
数据结构 上机实验题及题解
数据结构(c语言版)课后习题答案完整版
数据结构上机题目
严蔚敏数据结构题集(C语言版)完整
数据结构上机实验答案
数据结构上机题库
相关主题
文本预览