填空题
算法效率的比较
假设为解决某问题而设计的若干算法的时间复杂度分别为：
A) O(n)
B) O(n2)
C) O(log2n)
D) O(nlog2n)
E) O(2n)
F) O(√n)
G) O(n!)
H) O(1)
I) O(n√n)
J) O(n^n)
这些算法按效率由高到低的顺序是 HCFADIBEGJ
基本术语
算法 是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
算法的量度
(1) 算法所需执行时间的量度称为 时间复杂度
(2) 算法所需存储空间的量度称为 空间复杂度
在长度为n的顺序表L中将所有值为x的元素替换成y，该算法的时间复杂度为 O(n)
顺序表 - 地址计算
假设顺序表第 1 个元素的内存地址是 100，每个元素占用 2 字节内存空间，则第 5 个元素的内存地址是108
程序填空题
测量算法的运行时间
下面的程序测量某个函数 F 的运行时间。
请在空白处填写适当内容，完成该程序。
#include <stdio.h>
#include < time.h >
int F(int x);
int main()
{
int x, y;
clock_t t1, t2;
double t;
scanf("%d", &x);
t1 = clock() ;
y = F(x);
t2 = clock() ;
t = (t2 - t1) / (double)CLOCKS_PER_SEC ;
printf("%d\n", y);
printf("It took %.2f second(s).\n", t);
return 0;
}
int F(int x)
{
...(略)...
}
输入样例
25输出样例
3712
It took 0.18 second(s)注：图中数据仅为样例，实际结果可能不同。
顺序表插入操作
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype *elem;
int length;
} SqList;
int ListInsert_Sq(SqList &L, int i, datatype e) {
if ((i < 1) || (i > L.length + 1))
return ERROR;
if (L.length == MAXSIZE)
return ERROR;
for (int j = L.length - 1; j >= i - 1; j--)
L.elem[j + 1] = L.elem[j]; //2分
L.elem[i - 1] = e; //2分
++L.length;
return OK;
}
int main() {
SqList L;
int i = 0, n,a;
datatype e;
L.elem = new datatype[MAXSIZE];
L.length = 0;
cin >> n;
for (i=0;i<n;i++)
cin >> L.elem[i];
L.length = i;
cin >> a >> e;
if (ListInsert_Sq(L, a, e))
{
for (i = 0; i < L.length; i++)
if(i==0)
cout << L.elem[i];
else
cout << " " << L.elem[i];
}文章来源地址https://www.toymoban.com/news/detail-768390.html
else
cout << "ERROR";
return 0;
}
顺序表删除操作
#include<iostream>
using namespace std;
#define OK 1
#define ERROR 0
#define MAXSIZE 100
typedef int datatype;
typedef struct {
datatype *elem;
int length;
} SqList;
int ListDelete_Sq(SqList &L, int i) {
if ((i < 1) || (i > L.length))
return ERROR;
for (int j = i; j <= L.length; j++)
L.elem[j-1] = L.elem[j];
--L.length;
return OK;
}
int main() {
SqList L;
int i = 0, n,a;
datatype e;
L.elem = new datatype[MAXSIZE];
L.length = 0;
cin >> n;
for (i=0;i<n;i++)
cin >> L.elem[i];
L.length = i;
cin >> a;
if (ListDelete_Sq(L, a))
{
for (i = 0; i < L.length; i++)
if(i==0)
cout << L.elem[i];
else
cout << " " << L.elem[i];
}文章来源：https://www.toymoban.com/news/detail-768390.html
else
cout << "ERROR";
return 0;
}
单链表逆转
下列代码的功能是返回带头结点的单链表L的逆转链表。
List Reverse( List L )
{
Position Old_head, New_head, Temp;
New_head = NULL;
Old_head = L->Next;
while ( Old_head ) {
Temp = Old_head->Next;
Old_head->Next = New_head;
New_head = Old_head;
Old_head = Temp;
}
L->Next = New_head;
return L;
}
Prim
下列代码的功能是使用Prim算法求出无向图的最小生成树权值总和，请补全。
给出的图用邻接矩阵存储。若两顶点之间没有直接路径，则对应权值为 INF，且题目保证 INF 值足够大；若找不到距离最短的顶点或者无法求出权值总和，则返回 ERROR。
typedef int WeightType;
typedef int VertexType;
typedef struct {
int Nv;
WeightType G[MAX_GRAPH_SIZE][MAX_GRAPH_SIZE];
} GNode, * MGraph;
VertexType FindMinDist(MGraph Graph, WeightType dist[]) {
VertexType MinV = -1, V;
WeightType MinDist = INF;
for (V = 0; V < Graph->Nv; V++) {
if (dist[V] != 0 && dist[V] < MinDist 2分) {
MinDist = dist[V];
MinV = V; //2分
}
}
if (MinDist < INF) {
return MinV;
} else {
return ERROR;
}
}
int Prim(MGraph Graph) {
int dist[MAX_GRAPH_SIZE];
int TotalWeight = 0, VCount = 0;
VertexType V, W;
for (V = 0; V < Graph->Nv; V++) {
dist[V] = Graph->G[0][V];
}
dist[0] = 0;
VCount++;
while (1) {
VertexType MinV;
if ((MinV = FindMinDist(Graph, dist)) == ERROR) {
break;
}
TotalWeight += dist[MinV];
dist[MinV] = 0; //2分
VCount++;
for (W = 0; W < Graph->Nv; W++) {
if (dist[W] != 0 && dist[W] > Graph->G[MinV][W] 2分) {
dist[W] = Graph->G[MinV][W];
}
}
}
if (VCount < Graph->Nv 2分) {
return ERROR;
} else {
return TotalWeight;
}
}冒泡排序
本题要求用冒泡排序将一组整数按增序排序。冒泡排序每次从头到尾扫描待排序列，检查相邻两数的顺序，如果顺序不对就交换。请补全下列冒泡排序的代码。
typedef struct node *nodeptr;
struct node{
int value;
nodeptr next;
/* 一些其他的项，在此忽略 */
};
nodeptr BubbleSort (nodeptr h)
{/* h 是带空头结点的链表的头指针 */
nodeptr p, q;
int flag_swap;
if (!h->next) return h;
do{
flag_swap = 0;
p = h;
while (p->next->next){
if ( p->next->value > p->next->next->value 3 分 ){
flag_swap++;
q = p->next;
p->next = q->next 3 分;
q->next = p->next->next 3 分;
p->next->next = q 3 分;
}
else p = p->next;
}
} while (flag_swap > 0);
return h;
}
堆排序
下列代码的功能是利用堆排序将N个元素按非递减顺序排序。
#define leftchild(i) ( 2*(i)+1 )
void PercDown( ElementType A[], int i, int N )
{ int child;
ElementType Tmp;
for ( Tmp = A[i]; leftchild(i) < N; i = child ) {
child = leftchild(i);
if (child != N - 1 && A[child + 1] > A[child] 3 分)
child ++;
if (Tmp < A[child] 3 分) A[i] = A[child];
else break;
}
A[i] = Tmp 3 分;
}
void Heapsort( ElementType A[ ], int N )
{ int i;
for ( i = N / 2; i>= 0; i -- ) /* BuildHeap */
PercDown( A, i, N );
for ( i = N-1; i >0; i -- ) {
Swap( &A[ 0 ], &A[ i ] );
PercDown( A, 0, i ) 3 分;
}
}
希尔排序的分步结果
本题要求给出希尔排序对给定初始序列{9, 8, 7, 6, 5, 4, 3, 2, 1}利用增量序列{1, 3, 7}进行排序的分步结果。将每步结果填在下列空中。注意：相邻数字间必须有一个空格，开头结尾不得有多余空格。
原始序列 |
9 8 7 6 5 4 3 2 1 |
增量7排序后 |
2 1 7 6 5 4 3 9 8 1 分 |
增量3排序后 |
2 1 4 3 5 7 6 9 8 1 分 |
增量1排序后 |
1 2 3 4 5 6 7 8 9 |
初始化循环队列，判空队列
本题目要求Init_SeQueue()函数初始化循环队列，返回指向队列的指针，Empty_SeQueue(c_SeQueue *q)函数判空队列，空队列返回1。否则返回0。
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 1024
typedef int datatype;
typedef struct {
datatype data[MAXSIZE]; /*数据的存储区*/
int front,rear; /*队头队尾指针*/
int num; /*队中元素的个数*/
}c_SeQueue; /*循环队*/
c_SeQueue* Init_SeQueue()
{
c_SeQueue *q;
q=(c_SeQueue*)malloc(sizeof(c_SeQueue));
q->front=q->rear=MAXSIZE-1 3 分;
q->num=0;
return q;
}
int Empty_SeQueue(c_SeQueue *q)
{
if (q->num==0 3 分) return 1;
else return 0;
}
出循环队列
本题目要求Out_SeQueue (c_SeQueue *q , datatype *x)函数将 出循环队列的值送给变量x。出队成功返回1，否则返回-1。
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 1024
typedef int datatype;
typedef struct {
datatype data[MAXSIZE]; /*数据的存储区*/
int front,rear; /*队头队尾指针*/
int num; /*队中元素的个数*/
}c_SeQueue; /*循环队*/
int Out_SeQueue (c_SeQueue *q , datatype *x)
{
if (q->num==0)
{
printf("The c+SeQueue is empty");
return -1;
}
else
{
q->front=(q->front+1) % MAXSIZE 3 分;
*x=q->data[q->front];
q->num-- 3 分;
return 1;
}
}
到了这里，关于数据结构复习题——填空题与程序填空题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
