当前位置：文档之家 › 数据结构和C++程序设计_题库

数据结构和C++程序设计_题库

  • 格式：doc
  • 大小：250.00 KB
  • 文档页数：20

下载文档原格式

  / 20

合集下载

数据结构c语言期末考试题及答案

数据结构c语言期末考试题及答案

数据结构c语言期末考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。

A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一关系D. 结构中元素之间是否有一对多关系答案：C2. 线性表的顺序存储结构和链式存储结构相比，其优点是（）。

A. 存储密度高B. 存储密度低C. 插入和删除操作快D. 存储空间可以动态分配答案：A3. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数为（）。

A. i-1B. n-iC. n-i+1D. n-i-1答案：B4. 栈的运算遵循（）原则。

A. 先进先出B. 先进后出C. 后进先出D. 后进后出答案：C5. 在二叉树的前序遍历中，访问顺序为（）。

A. 根-左-右B. 左-根-右C. 左-右-根D. 右-左-根答案：A6. 哈希表的冲突解决方法中，链地址法是（）。

A. 将所有元素存储在同一个存储单元B. 将所有元素存储在同一个链表中C. 将所有元素存储在同一个数组中D. 将所有元素存储在同一个链表的同一个位置答案：B7. 在图的遍历中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 遍历的顺序不同B. 遍历的起点不同C. 遍历的路径不同D. 遍历使用的存储结构不同答案：D8. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B9. 归并排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 在二叉搜索树中，查找一个元素的时间复杂度为（）。

A. O(n)B. O(logn)C. O(n^2)D. O(1)答案：B二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度通常用______来描述。

答案：大O符号2. 线性表的两种基本操作是插入和______。

数据结构(C语言)【经典题库】含答案

数据结构(C语言)【经典题库】含答案

数据结构(C语言)【经典题库】含答案数据结构（C语言）【经典题库】含答案数据结构是计算机科学中的重要基础，对于程序员和软件工程师来说，熟练掌握数据结构是必不可少的。

在C语言中，有许多经典的数据结构题目，通过解答这些题目，可以深入理解数据结构的原理和应用。

本文将介绍一些经典的数据结构题目，同时附上详细的答案。

一、数组题目1. 给定一个整型数组arr和一个整数target，找出数组中两个数的和为target的所有组合。

```C#include <stdio.h>void findPairs(int arr[], int n, int target) {int i, j;for (i = 0; i < n - 1; i++) {for (j = i + 1; j < n; j++) {if (arr[i] + arr[j] == target) {printf("%d, %d\n", arr[i], arr[j]);}}}}int main() {int arr[] = {2, 4, 6, 8, 10};int target = 14;int n = sizeof(arr) / sizeof(arr[0]);findPairs(arr, n, target);return 0;}```答案解析：使用两层循环遍历数组中的每对元素，判断它们的和是否等于目标值target，如果是则输出。

时间复杂度为O(n^2)。

2. 给定一个整型数组arr和一个整数k，求出数组中连续子数组的最大和。

```C#include <stdio.h>int maxSubArraySum(int arr[], int n) {int maxSum = arr[0];int currentSum = arr[0];for (int i = 1; i < n; i++) {currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] : arr[i];if (currentSum > maxSum) {maxSum = currentSum;}}return maxSum;}int main() {int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};int n = sizeof(arr) / sizeof(arr[0]);int maxSum = maxSubArraySum(arr, n);printf("最大和为：%d\n", maxSum);return 0;}```答案解析：使用动态规划的思想，定义两个变量`maxSum`和`currentSum`，分别表示当前的最大和和累加和。

数据结构c语言期末考试题库及详解答案

数据结构c语言期末考试题库及详解答案

数据结构c语言期末考试题库及详解答案数据结构C语言期末考试题库及详解答案一、选择题1. 在数据结构中，线性表的顺序存储结构被称为：A. 链式存储结构B. 栈C. 队列D. 数组答案：D2. 下列关于栈的描述，错误的是：A. 栈是一种特殊的线性表B. 栈的特点是后进先出C. 栈顶元素是最后插入的元素D. 栈的插入和删除操作都发生在栈顶答案：C二、填空题1. 在C语言中，定义一个具有10个元素的整型数组可以使用语句：________。

答案：int arr[10];2. 链表与数组相比，其优点是________。

答案：动态内存分配，不需要预先知道数据规模三、简答题1. 简述二叉树的遍历方法有哪些，并说明它们的特点。

答案：二叉树的遍历方法主要有前序遍历、中序遍历和后序遍历三种。

前序遍历首先访问根节点，然后递归地遍历左子树和右子树；中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树；后序遍历首先遍历左子树和右子树，最后访问根节点。

每种遍历方法都可以用来对二叉树进行不同的操作和分析。

2. 什么是哈希表？它在实际应用中有哪些优点？答案：哈希表是一种通过哈希函数将键映射到表中一个位置来访问记录的数据结构。

它的优点包括：快速的数据访问速度，因为哈希表通常在常数时间内完成查找；动态的内存分配，可以根据需要调整存储空间；以及灵活的键值对存储方式。

四、编程题1. 编写一个C语言函数，实现单链表的逆序输出。

答案：```c#include <stdio.h>#include <stdlib.h>typedef struct Node {int data;struct Node *next;} Node;void reversePrint(Node *head) {if (head == NULL) return;reversePrint(head->next);printf("%d ", head->data);}int main() {Node *head = (Node *)malloc(sizeof(Node));head->data = 1;head->next = NULL;// 假设链表已经构建完毕reversePrint(head);return 0;}```2. 请实现一个C语言函数，用于计算一个字符串中不同字符的数量。

数据结构试题及答案c语言版

数据结构试题及答案c语言版

数据结构试题及答案c语言版一、选择题（每题2分，共20分）1. 在C语言中，以下哪个选项是正确的链表定义？A. struct Node { int data; struct Node *next; };B. struct Node { int data; Node *next; };C. struct Node { int data; struct Node *next; } *Node;D. struct Node { int data; Node *next; };答案：A2. 下列关于栈的描述中，错误的是？A. 栈是一种后进先出（LIFO）的数据结构。

B. 栈的插入操作称为push。

C. 栈的删除操作称为pop。

D. 栈可以存储任意数量的数据。

答案：D3. 在C语言中，以下哪个关键字用于定义一个结构体？A. structB. unionC. enumD. typedef答案：A4. 下列关于队列的描述中，正确的是？A. 队列是一种先进先出（FIFO）的数据结构。

B. 队列只能从队尾进行插入操作。

C. 队列的插入操作称为pop。

D. 队列的删除操作称为push。

答案：A5. 在C语言中，以下哪个函数用于创建一个动态数组？A. mallocB. callocC. reallocD. all of the above答案：D6. 下列关于二叉树的描述中，错误的是？A. 二叉树的每个节点最多有两个子节点。

B. 二叉树的子节点被称为左子树和右子树。

C. 二叉树的遍历方式包括前序、中序、后序。

D. 二叉树的每个节点只能有一个子节点。

答案：D7. 在C语言中，以下哪个函数用于释放动态分配的内存？A. freeB. mallocC. callocD. realloc答案：A8. 下列关于图的描述中，错误的是？A. 图是由顶点和边组成的数据结构。

B. 图的边可以是有向的，也可以是无向的。

C. 图的顶点可以是孤立的，没有边与之相连。

数据结构及程序设计考题

数据结构及程序设计考题

考试内容：1. 算法的基本概念；算法复杂度的概念和意义（时间复杂度和空间复杂度）2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。

3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。

4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。

5.线性单链表、双向链表与循环链表的结构及其基本运算。

6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。

7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。

2005年4月（14分）（1）数据的存储结构是指______。

A）存储在外存中的数据B）数据所占的存储空间量C）数据在计算机中的顺序存储方式D）数据的逻辑结构在计算机中的表示答案：D（2）下列关于栈的描述中错误的是______。

A）栈是先进后出的线性表B）栈只能顺序存储C）栈具有记忆作用D）对栈的插入与删除操作中，不需要改变栈底指针答案：B（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是______。

A）冒泡排序为n/2 B）冒泡排序为nC）快速排序为n D）快速排序为n(n-1)/2答案：D冒泡排序为n(n-1)/2（4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为______。

A）log2n B）n/2 C）n D）n+1答案：C（5）下列对于线性链表的描述中正确的是______。

A）存储空间不一定是连续，且各元素的存储顺序是任意的B）存储空间不一定是连续，且前件元素一定存储在后件元素的前面C）存储空间必须连续，且前件元素一定存储在后件元素的前面D）存储空间必须连续，且各元素的存储顺序是任意的答案：A（47）有以下结构体说明和变量定义，如图所示：struct node{int data; struct node *next;} *p,*q,*r;p q r现要将q所指结点从链表中删除，同时要保持链表的连续，以下不能完成指定操作的语句是______。

数据结构与C语言程序设计试题及答案

数据结构与C语言程序设计试题及答案
5．已知模式匹配的KMP算法中模式串t=’adabbadada’，其next函数的值为0112112343。
6．在置换-选择排序中，假设工作区的容量为w，若不计输入、输出的时间，则对n个记录的文件而言，生成所有初始归并段所需时间为O(n log w)。
三.简答题（6’5）
1．有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序方法时间复杂度最佳？为什么？
采用基数排序方法最佳。
因单词长度相等，而只有26个字母组成，符合基数排序的条件。
因m<<n，故时间复杂性由O(m(n+rm))变成O(n)。
2．对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。若输入序列的长度为n，则可能的输出序列有多少？
ABC，ACB，BAC，BCA，CBA
C2nn/（n+1）
（）10、任何有向图的顶点都可以按拓扑序排序。
二.填空题（2’6）
1．假设用于通信的电文由8个字母组成，其频率分别为0.07，0.19,0.02,0.06, 0.32,0.03,0.21,0.10,为这8个字母设计哈夫曼编码，其中编码长度最大的字母的编码是5位。
2．已知二叉树按中序遍历所得到的结点序列为DCBGEAHFIJK，按后序遍历所得到的结点序列为DCEGBFHKJIA，按先序遍历所得到的结点序列为ABCDGEIHFJK。
O(n log n)
四.程序设计题（38’）
1．假设有两个集合A和B，均以元素值递增有序排列的带头结点的单链表作为存储结构。请编写算法求C=AB，要求C按元素值递增有序排列，并要求利用原表（即表A和表B）的结点空间存放表C。(12’)
void Join(LinkList &la , LinkList &lb , LinkList &lc)

C程序设计编程题库

C程序设计编程题库

C程序设计编程题库C程序设计编程题库顺序结构编程1.输入两个整数A和B，将它们交换（即A的值给B，B的值给A）后输出A和B。

2.输入三个整数A、B和C，将它们交换（即A的值给B，B的值给C，C的值给A）后输出A、B和C。

3.输入1个三位正整数N，输出其个位、十位和百位。

4.输入一个英文字符，输出其ASCII码。

分支结构（IF）：1.输入一个正整数，判断是奇数或偶数、负数或非负数。

2.输入一个1-1000之间的数，判断是几位数。

3.输入一个字符，判断是大写字母、小写字母、数字或其他。

4.输入一个年份，判断是否为闰年。

（凡是能被400整除的年份为闰年。

如2000年；凡是不能被100整除，但能被4整除的年份为闰年。

如2008年）5.已知三角形三条边的长度，求三角形的面积。

6.已知一元二次方程的三个系数，求方程的根。

7.输入三个整数，分别赋给X、Y、Z，然后按从小到大的顺序输出这三个变量的值。

8.输入一个三位数，判断其是否为水仙花数。

如153，因为153=13+53+33分支结构（switch）：1.输入一个1至7之间的数字，输出星期日至星期六。

2.输入一个月份，输出该月的天数。

循环结构（用while 和do …while 两种方法）1. 编写程序求sum=1+2+3+……+100的值（教科书例题）2. 编写程序求10！=1*2*3*……*10的值3. 输入N ，求N ！=1*2*3*……*N 的值4. 输入自然数N ，输出N 的位数。

5. 求满足条件1+2+3+…+N<100000的最大N 。

（教科书例题）6. 求满足条件1+2+3+…+N>100000的最小N 。

7. 输入一个整数，求它的各位数字之和。

（教科书例题）8. 采用欧几里得算法，求两个自然数的最大公约数。

（教科书例题）9. 求两个自然数的最小公倍数。

M 与N 的最小公倍数=的最大公约数和N M N M * 10. 输入一行字符，统计大写字母、小写字母、数字及其它符号的个数（实验15.3.3）11. 用牛顿迭代法求方程2x 3-4x 2+3x-6=0在1.5附近的根。

河南师范大学846数据结构与C程序设计

河南师范大学846数据结构与C程序设计

来源网络，造福学生———————欢迎下载，祝您学习进步，成绩提升———————2018年攻读硕士学位研究生入学考试试题科目代码与名称：846数据结构与C程序设计适用专业或方向：计算机科学与技术（各方向）考试时间：3小时满分：150分试题编号：B（必须在答题纸上答题，在试卷上答题无效，答题纸可向监考老师索要）第一部分数据结构（80分）B卷一、单项选择题（20个选题，每选题2分，共40分）（备注：答题时每连续的5个为一组，组与组之间要留有空隙,例如，ACCCD ACDAC)1.从逻辑结构来说，栈属于OA.树形结构B.散列表结构C.线性结构D.图状结构2.程序段for (i=0,k=0; i<100; i++)for (j=0; j<10000; j++) k++;的时间复杂度是。

A.0(1)B. 0(n*m)C. 0(n+m)D. 0(Max(n, m))3.若线性表釆用顺序存储结构，则在删除一个元素时需要移动的元素的次数与有关。

A.首地址B.元素的值C.线性表的有序性D.删除位置4.在一个带头结点的表长为5的循环单链表中，若其头指针为L,则在它的第一个元素结前插入S所指结点，则执行OA.s->next=L->next; L->next=s；B. L->next=s-〉next-〉next；C. s->next=L->next~>next； L~>next=sD. s->next=L-〉next； L->next=L;5.队列操作的特征是oA.先进先出B.先进后出C.插入在队头D.删除的是队尾6.在递归程序的执行过程中要用到。

A.栈B.循环结构C.顺序结构D.队列第1页，共7页7.用x表示入栈操作，用s表示出栈操作，若栈的初始状态为空，则下面—合法的操作序列。

A. xssssxxxB. xssxxsxxC. XXSXSSXD. SSSXXXXSSXX第2页，共7页第3页，共7页D. 19, 78, 32, 52, 12, 44, 66 .是错误的。

2010年硕士研究生入学考试“数据结构与C语言程序设计”试题与答案

2010年硕士研究生入学考试“数据结构与C语言程序设计”试题与答案

13．C 语言规定，简单变量做实参时，它和对应的形参之间的数据传递方式是 A．单向值传递 B．地址传递 C．由实参传给形参，再由形参传回给实参 D．由用户指定传递方式 14．C 语言规定，函数返回值的类型是由 A．return 语句中的表达式的类型所决定 B．调用该函数时的主函数的类型所决定 。
3
C．调用该函数时系统临时决定 D．在定义该函数时所指定的函数的类型所决定 15．下面给出的 4 个定义语句中，与 int *p[5]; 等价的是 。 A．int p[5]; B．int *p; C．int *(p[5]); 16．若有以下定义和语句，则值为 1002 的表达式是 。 struct s{ int age; int num; }; static struct s a[3]={1001,20,1002,19,1003,21},*ptr; ptr=a; A．ptr++->num B．(ptr++)->age C．(*ptr).num D．(*++ptr).age 17．若要通过下面的程序段使得指针变量指向一个存储整型变量的动态存储单元，则程序段中的空 。 白处(横线上方)应该是 int *ptr; ptr= malloc(sizeof(int)); A．int B．int * C．(int *) D．(*int ) 。 18．下面关于宏的叙述中，错误的是 A．宏名无类型，其参数也无类型 B．宏定义不是 C 语句，不必在行的末尾加分号 C．宏替换只是字符替换 D．宏定义命令必须写在文件的开头 。 19．下列关于 C 语言文件操作的叙述中，正确的是 A．对文件的操作必须是先打开文件 B．对文件的操作必须是先关闭文件 C．对文件操作之前必须先测试文件是否已打开，然后再打开文件 D．对文件的操作无顺序要求 20．使用 fopen( )函数以文本方式打开或者建立可读写文件。要求：若指定文件不存在，则建立一 个文件，并使文件指针指向其开头；若指定文件存在，则打开该文件，并将文件指针指向其结尾。下列 。 “文件使用方式”中，正确的是 A．“r+” B．“ a+” C．“ w+” D．“a”

C程序设计试题汇编

C程序设计试题汇编

c程序设计试题汇编C程序设计试题汇编一、选择题（每题2分，共20分）1. 在C语言中，以下哪个是正确的数据类型？A. IntegerB. intC. RealD. float2. 以下哪个语句可以正确地声明一个整型变量？A. int var;B. var int;C. int = var;D. var = int;3. C语言中的数组下标是从哪个数字开始的？A. 0B. 1C. -1D. 随机数4. 以下哪个是正确的C语言函数定义？A. int func(int a, int b) { return a + b; }B. int func(int, int) { return a + b; }C. func(int a, int b) { return a + b; }D. int func(a, b) { return a + b; }5. 在C语言中，哪个关键字用于定义一个函数？A. functionB. defC. defineD. void6. 以下哪个是C语言中的循环结构？A. forB. whileC. do-whileD. 所有选项都是7. 在C语言中，以下哪个操作符用于取模运算？A. %B. /C. *D. -8. 以下哪个是C语言中的逻辑运算符？A. &&B. ||C. ~D. 所有选项都是9. 在C语言中，哪个关键字用于定义一个结构体？A. structB. typeC. classD. union10. 以下哪个是C语言中的输入输出函数？A. printf()B. print()C. input()D. read()二、填空题（每空2分，共20分）11. 在C语言中，字符常量用____表示。

12. 一个C语言程序的执行从____函数开始。

13. C语言中的字符串以____字符结尾。

14. 一个变量的存储类别可以是自动的（auto）或____的。

15. 在C语言中，____运算符用于连接字符串。

数据结构c语言版题集

数据结构c语言版题集

数据结构c语言版题集
数据结构是计算机科学中非常重要的一个领域，它研究如何组织和存储数据以及对数据进行操作和处理。

C语言是一种广泛应用于系统编程和嵌入式开发的编程语言，非常适合实现和操作各种数据结构。

下面是一些常见的数据结构题目，以C语言为基础进行实现和练习。

1. 数组操作：
实现一个函数，用于在给定的数组中查找特定元素的位置。

实现一个函数，用于在给定的数组中删除指定位置的元素。

实现一个函数，用于在给定的数组中插入一个元素到指定位置。

2. 链表操作：
实现一个函数，用于在给定的链表中查找特定元素的位置。

实现一个函数，用于在给定的链表中删除指定位置的节点。

实现一个函数，用于在给定的链表中插入一个节点到指定位置。

3. 栈和队列：
实现一个栈数据结构，包括入栈、出栈和获取栈顶元素的操作。

实现一个队列数据结构，包括入队、出队和获取队首元素的操作。

4. 树和二叉树：
实现一个二叉树数据结构，并实现前序、中序和后序遍历算法。

实现一个二叉搜索树数据结构，并实现插入和删除节点的操作。

5. 图：
实现一个图数据结构，并实现深度优先搜索和广度优先搜索
算法。

实现一个最短路径算法，如Dijkstra算法或Floyd-Warshall算法。

以上仅是一些常见的数据结构题目示例，你可以根据自己的实
际需求和学习进度选择适合的题目进行练习。

在实现过程中，要注
意正确的内存管理和算法复杂度的考虑，以保证代码的效率和质量。

希望这些题目对你的学习有所帮助！。

数据结构习题库(c语言版)

数据结构习题库(c语言版)

第一章绪论一、基本内容数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义、抽象数据类型的定义、表示和实现方法、描述算法的类C语言、算法设计的基本要求。

二、学习要点1、熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2、了解抽象数据类型的定义、表示和实现方法。

3、熟悉类C语言的书写规范，特别要注意值调用和引用调用的区别，输入、输出的方式以及错误处理方式。

4、理解算法五个要素的确切含义。

1.1 基础知识一、填空题1、数据的逻辑结构包括①，②，③和④四种类型，树型结构和图型结构合称为⑤，数据的存储结构即物理结构包括：⑥，⑦等两种基本类型。

2、在线性结构中元素之间存在①关系，树形结构中元素间存在②关系，图形结构中元素间存在③关系。

3、一个数据结构用二元组表示时，它包括①集合D和D上②的集合S。

4、一个算法应具有①，②，③，④和⑤这五个特性。

5、在图形结构中，每个节点的前驱节点和后继节点可以有①个。

6、一个抽象数据类型用三元组（D，S，P）表示时，D是①，S是②，P是③。

7、数据元素在计算机中的映象是①。

8、算法的设计取决于①，算法的实现取决于②。

二、选择题1、数据元素是数据的单位。

(A)基本(B)最小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)哈夫曼树解答：一、填空题1、①线性 ②集合 ③树 ④图或网 ⑤非线性结构 ⑥顺序存储 ⑦链式存储2、①1：1 ②1：n ③m ：n3、①数据元素 ②关系4、①有穷性 ②确定性 ③可行性 ④输入 ⑤输出5、①多个6、①数据对象 ②D 上的关系集合 ③对D 的基本操作集合7、①元素或结点8、①数据（逻辑）结构 ②采用的存储结构二、 选择题1、A2、B3、C4、B5、B6、Al.2 应用知识1、什么是算法？算法的特性是什么？算法设计的要求是什么?解答: （略）2、设有数据结构USER_STRU 表示如下：USER_STRU =（D ，S ）D = { a1，a2，…，a9 }S = { <a1，a3>，<a1，a8>，<a2，a3>，<a2，a4>，<a2，a5>，<a3，a9>，<a5，a6>，<a8，a9>，<a9，a7>，<a4，a7>，<a4，a6> }画出这个数据结构的图示，并确定其类型。

数据结构与C语言综合训练习题集

数据结构与C语言综合训练习题集

数据结构与C语言综合训练习题集序号项目名称任务描述设计要求每组学生人数1．订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：确定航班是否满仓）；可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

修改航班信息：当航班信息改变可以修改航班数据文件根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；2．用Haffman编码压缩文件准备一个文件，统计该文件中各种字符的频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。

3．统计C程序中关键字的频率扫描一个C源程序，用Hash表存储该程序中出现的关键字，并统计该程序中的关键字出现频度。

用线性探测法解决Hash冲突。

设Hash函数为：Hash(key)=[(key的第一个字母序号)*100+(key的最后一个字母序号)] MOD 374．商品管理系统以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。

链表结构的数据域包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。

程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据与文件之间的转换等。

5．排序算法效率比较编程实现插入、希尔、快速、堆排序、归并排序算法，并计算每种算法的比较、交换次数。

将待排数据从磁盘文件读入，实施排序后将数据写入另一个文件中。

数据结构基础、程序设计基础、软件工程基础、数据库基础知识带解析题库

数据结构基础、程序设计基础、软件工程基础、数据库基础知识带解析题库

第一章数据结构一、选择题（1）下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表 B）线性链表C）二叉链表 D）有序线性链表【答案】A【解析】二分查找只适用于顺序存储的有序表。

在此所说的有序表是指线性表中的元素按值非递减排列(即从小到大．但允许相邻元素值相等)的。

选项A正确。

（2）下列关于栈的描述正确的是A）在栈中只能插入元素而不能删除元素B）在栈中只能删除元素而不能插入元素C）栈是特殊的线性表，只能在一端插入或删除元素D）栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素【答案】C【解析】栈是一种特殊的线性表，其插入与删除运算都只在线性表的一端进行。

由此可见，选项A、选项B和选项D错误，正确答案是选项C。

（3）下列叙述中正确的是A）一个逻辑数据结构只能有一种存储结构B）数据的逻辑结构属于线性结构，存储结构属于非线性结构C）一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率D）一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率【答案】D【解析】一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。

而采用不同的存储结构，其数据处理的效率是不同的。

由此可见，选项D的说法正确。

(4)算法执行过程中所需要的存储空间称为算法的A）时间复杂度B）计算工作量C）空间复杂度D）工作空间【答案】c【解析】算法执行时所需要的存储空间，包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间，其中额外空间还包括算法程序执行过程的工作单元以及某种数据结构所需要的附加存储空间。

这些存储空间共称为算法的空间复杂度。

(5)下列关于队列的叙述中正确的是A）在队列中只能插入数据B）在队列中只能删除数据C）队列是先进先出的线性表D）队列是先进后出的线性表【答案】c【解析】对队列可以进行插入和删除数据的操作，只是插入数据只能在队尾，删除数据只能在队头。

数据结构题集c语言版考试题及答案

数据结构题集c语言版考试题及答案

数据结构题集c语言版考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构是指（）。

A. 用一组地址连续的存储单元依次存储线性表的元素B. 用一组地址不连续的存储单元依次存储线性表的元素C. 用数组来存储线性表的元素D. 用链表来存储线性表的元素答案：A2. 在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动（）个元素。

A. i-1B. n-iC. n-i+1D. i答案：B3. 对于一个有n个结点的线性表，采用链式存储结构时，进行查找第i个元素（1≤i≤n）的时间复杂度为（）。

A. O(1)B. O(n)C. O(log2n)D. O(n^2)答案：B4. 在二叉树的遍历过程中，若一个结点的左子树为空，则该结点的右子树（）。

A. 一定为空B. 一定不为空C. 可能为空，也可能不为空D. 以上说法都不对答案：C5. 在二叉排序树中，若某结点的左子树非空，则左子树中的所有结点的值（）。

A. 都小于该结点的值B. 都大于该结点的值C. 都等于该结点的值D. 都大于等于该结点的值答案：A6. 一个具有n个顶点的连通图，其边数最少为（）。

A. n-1B. nC. n+1D. 2n答案：A7. 在图的遍历中，深度优先搜索算法所对应的数据结构是（）。

A. 栈B. 队列C. 链表D. 数组答案：A8. 哈希表的冲突解决方法中，开放定址法的特点是（）。

A. 装填因子较大B. 装填因子较小C. 装填因子不受限制D. 以上说法都不对答案：B9. 快速排序算法的时间复杂度为（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(logn)答案：B10. 用链表表示线性表的优点是（）。

A. 插入和删除操作不需要移动元素B. 节省存储空间C. 可以方便地随机访问D. 可以动态分配存储空间答案：A二、填空题（每题2分，共20分）1. 在顺序表中，若p是指向第i个元素的指针，则p+5表示指向第（）个元素的指针。

c程序设计考试题库及答案

c程序设计考试题库及答案

c程序设计考试题库及答案1. 以下哪个选项是C语言中正确的整型常量表示方式？A. 0x1AB. 1.5e2C. 0b1010D. 07777答案：A2. 在C语言中，以下哪个关键字用于定义一个结构体？A. structB. unionC. enumD. typedef答案：A3. 以下哪个选项是C语言中合法的变量名？A. 2variableB. variable-nameC. _variableD. $variable答案：C4. 在C语言中，以下哪个函数用于计算并返回字符串的长度？A. strlenB. strcpyC. strcatD. strcmp答案：A5. 以下哪个选项是C语言中正确的二维数组声明方式？A. int array[3][4];B. int array[][];C. int array[3][];D. int array[4,3];答案：A6. 在C语言中，以下哪个关键字用于声明一个无限循环？A. forB. whileC. do-whileD. switch答案：B7. 以下哪个选项是C语言中正确的函数声明方式？A. int function(int a, int b);B. int function(int, int);C. int function(a, b);D. int function();答案：A8. 在C语言中，以下哪个运算符用于取模运算？A. %B. //C. //D. /答案：A9. 以下哪个选项是C语言中正确的宏定义？A. #define PI 3.14159B. #define PI = 3.14159C. #define PI 3.14159D. #define PI 3.14159;答案：A10. 在C语言中，以下哪个关键字用于声明一个指针变量？A. intB. floatC. charD. void答案：D。

程序设计与数据结构练习题 附答案

程序设计与数据结构练习题 附答案

一、单项选择题1．有下列程序段落:int i,a[5]；for(i=0;i<5;i++)scanf(“%d”,&a[i]);若要使数组元素的值分别为1，2，3，4，5，应从键盘输入（B）。

Ａ．1,2,3,4,5↙Ｂ．1 2 3 4 5↙Ｃ．12345↙Ｄ．1;2;3;4;5↙2．数组名作为函数参数进行传递时，形参获得的是（D）。

A．该数组第一个元素的值B．该数组所有元素的值C．该数组所有元素的地址D．该数组的首地址3.设有如下宏定义:#define A 3+2#define B A*A则表达式“B*B”的值为（ A ）。

Ａ．23Ｂ．5 Ｃ．25Ｄ．6254．在下列说明中，结构类型变量x 所占用内存字节数为（D）。

struct exp{ int i;float j;double k;}x;Ａ．8个Ｂ．7个Ｃ．14个Ｄ．随计算机而定5．设有定义：int k=3,*p=&k; 则表达式*p的值是（D）。

Ａ．1 Ｂ．0 Ｃ．2 Ｄ．36．下列程序的输出结果为（A）。

main（）{ int i=3，b；b=(i--)+(i--)；printf（“%d”，b）；}Ａ．6 Ｂ．2 Ｃ．3 Ｄ．47．当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是（D）。

Ａ．c=b=a Ｂ. (a=c)||(b=c) Ｃ. a=c=b Ｄ. (a=c)&&(b=c)8．下列叙述不正确的是（ A ）。

Ａ．函数定义可以嵌套Ｂ．宏定义可以嵌套Ｃ．函数调用可以嵌套Ｄ．循环结构可以嵌套9．设char *p=“abcde”，则printf(“%s”, p ) 的输出结果为（ D ）。

Ａ．c Ｂ．cde Ｃ．b Ｄ．abcde10．p1,p2 为指向浮点的指针变量，下列运算没有意义的是（D）。

Ａ．*p1－*p2 Ｂ．p1++ Ｃ．*p1+*p2 Ｄ．p1+p211．设有int i=010,j=10; 则printf( “%d,%d\n”,++i,j--);的输出是（B）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

《数据结构》Part1一．选择1. 组成数据的基本单位是（）A）数据项B）数据类型C）数据元素D）数据变量2．算法分析的目的是（）A）找出数据结构的合理性B）研究算法的输入/输出关系C）分析算法的效率以求改进D）分析算法的易读性3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n)4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（）A）112 B）144 C）148 D）4125．下面关于线性表的叙述中，错误的是（）A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元.C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适A）单链表B）双链表C）顺序表D）循环链表7．队列通常采用的两种存储结构是（）A）顺序存储结构和链式存储结构B）散列方式和索引方式C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构8．在一个单链表中，若删除p所指结点的后继结点，则执行（）A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next；C）p->next=p->next；D）p=p->next->next；9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表10．按二叉树的定义，具有三个结点的二元树共有（）种形态。

A）3 B）4 C）5 D）611．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点A）16 B）32 C）31 D）1013．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。

A）4 B）5 C）6 D）714．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（）A）n B）n+1 C）n-1 D）n/215．静态查找表和动态查找表二者的根本差别在于（）A）它们的逻辑结构不同B）施加在其上的操作不同C）所包含的数据元素的类型不一样D）存储实现不一样二．填空1．某程序的时间复杂性为(3n+nlog2n+n2+8),其数量级表示为________。

2．线性表L=(a1,a2,…,an)采用顺序结构存储,假定在不同的位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是_________。

3.对于一株具有n个结点的树，该树中所有结点的度数之和为______。

4. 在一个图中,所有顶点的度数之和等于所有边数的______________倍。

5. 一棵二叉树有67个结点,这些结点的度要么是0，要么是2。

这棵二元树中度数为2的结点有______________个。

6．在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是_____。

7．采用堆排序、快速排序、冒泡排序，对初态有序的表，最省时间的是______ 。

8．设二叉树结点的先根序列为ABDECFGH，中根序列为DEBAFCHG,则二元树中叶结点是_________.9．一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是______。

10.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1，则栈S至少应该容纳_______个元素。

三．判断1．线性表的链式存储结构优于顺序行储结构。

（）2．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

（）3．对于n个记录的集合进行归并排序，存最坏的情况下所需要的时间是O(n^2)。

（）4．表中的每一个元素都有一个前驱和后继元素。

（）5．进栈操作push(x，s)作用于链接栈时，无须判满。

（）6．只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。

（）7．在索引顺序表查找方法中，对索引顺序表可以使用顺序表查找方法，也可以使用二分查找方法。

（）8．数据元素是数据的最小单位。

（）9．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（）10．按中序遍历一棵二叉排序树所得到的中序遍历序列是一个递增序列。

（）四．简答1. 对于下图所示的树：(1) 写出先序遍历得到的结点序列；(2) 画出转换后得到的二叉树。

2．请画出与下列二元树对应的森林。

五．算法设计1．已知一个int类型的数组arra，其长度为n，要求用冒泡排序算法对其从小到大排序，请实现该算法，（要求后面开始循环，大的数值下沉）。

2．利用一个栈实现以下递归函数的非递归计算：Pn (x)=⎪⎩⎪⎨⎧>==----11)()1(2)(22121nnnxPnxxPxnnPart2一、单项选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结构与外部结构B）静态结构与动态结构C）线性结构与非线性结构D）紧凑结构与非紧凑结构。

2、算法分析的目的是（）A）找出数据结构的合理性B）研究算法中输入和输出的关系C）分析算法的效率以求改进D）分析算法的易懂性和文档性3、在一个单链表中，若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;4、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。

A）起泡排序B）堆排序C）锦标赛排序D）快速排序5、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。

A）求子串B）模式匹配C）串替换D）串连接6、将一个递归算法改为对应的非递归算法时，通常需要使用（）。

A）栈B）队列C）循环队列D）优先队列7、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。

A）( front - rear + 1) % m B）( rear - front + 1) % mC）( front - rear + m) % m D）( rear - front + m) % m8、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)9、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。

A）s->link=p;p->link=s; B）s->link=p->link;p->link=s;C）s->link=p->link;p=s; D）p->link=s;s->link=p;10、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（）A）n-2 B）n-1 C）n D）n+111、某二叉树的前序和后序序列正好相反，则该二叉树一定是（）的二叉树。

A）空或只有一个结点B）高度等于其结点数C）任一结点无左孩子D）任一结点无右孩子12、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2，则( )A）n0= n2+1 B）n2= n0+1 C）n0= 2n2+1 D）n2=2n0+113、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A）24 B）73 C）48 D）5314、对线性表进行折半搜索时，要求线性表必须（）A）以链接方式存储且结点按关键码有序排列B）以数组方式存储C）以数组方式存储且结点按关键码有序排列D）以链接方式存储15、顺序搜索算法适合于存储结构为（）的线性表。

A）散列存储B）顺序存储或链接存储C）压缩存储D）索引存储二、填空1、数据的存储结构被分为、、、四种。

2、一种抽象数据类型包括和两个部分。

3、栈、队列逻辑上都是结构。

4、栈中存取数据的原则，队列中存取数据的原则。

5、设目标串T=”abccdcdccbaa”,模式P=”cdcc”则第次匹配成功。

三、判断1、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

( )2、线性表的逻辑顺序与物理顺序总是一致的。

（）3、每种数据结构都应具备三种基本运算：插入、删除、搜索。

（）4、深度为h的非空二叉树的第h层最多有2h-1个结点。

（）5、完全二叉树就是满二叉树。

（）6、最优二叉搜索树一定是平衡的二叉搜索树。

（）7、线性表中所有结点的类型必须相同。

（）8、连通分量是无向图中的极小连通子图。

（）9、空串与由空格组成的串没有区别。

（）10、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。

（）四、简答1、在结点个数为n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？2、将下面的森林变换成二叉树。

3、有图如下，请画出其邻接多重表。

五．算法设计1、编写算法实现链表的创建、遍历、销毁。

2、编写算法，实现快速排序。

Part3一．选择1、在数据结构的讨论中把数据结构从逻辑上分为（）A）内部结构与外部结构 B）静态结构与动态结构C）线性结构与非线性结构 D）紧凑结构与非紧凑结构。

2、下面程序段的时间复杂度为（）for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A）O(m2) B）O(n2) C）O(m*n) D）O(m+n)3、采用线性链表表示一个向量时，要求占用的存储空间地址（）A）必须是连续的 B）部分地址必须是连续的C）一定是不连续的 D）可连续可不连续4、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（）。

A）da1+(I-1)*m B）da1+I*m C）da1-I*m D）da1+(I+1)*m5．下面关于线性表的叙述中，错误的是（）A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域6、在一个单链表中，若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;7、设循环队列的结构如下：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（）A)Q.front = = Q.rear; B)Q.front - Q.rear= = Maxsize;C)Q.front + Q.rear = = Maxsize; D)Q.front= = (Q.rear+1)% Maxsize;8、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。