PTA程序填空题14道.pdf-资料库

2020/6/18 题目列表剩余时间:3天 CUIT通信2019级数据结构复习题（程序填空题）new 程序填空题 14 5-1 本题目要求判断输入的字符串中小括号是否配对。输入举例 shdlfa(aksjdhjf(jashdlf(sdjfhljasd)ahjsdhfha)hflajshdf) 输出举例字符串中的小括号是成对的作者单位时间限制内存限制 CUIT通信DS课程组成都信息工程大学 400 ms 64 MB https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 1/16 保存

2020/6/18 题目列表 DataType items[STACKSIZE]; /*存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标*/ 剩余时间:3天 return 0; /*栈已满*/ S->top = -1; return 1; if ( S->top == STACKSIZE-1) S->top++; S->items[S->top]=e; return 1; #include #include typedef char DataType; /*栈中允许存储的元素的最大个数*/ #define STACKSIZE 100 /* 顺序栈的定义 */ typedef struct { }SqStack; int InitSqStack(SqStack *S) { } int SqStackPush( SqStack *S, DataType e ) { } int SqStackPop(SqStack *S, DataType *e) { /* 将栈S的栈顶元素弹出，放到e所指的存储空间中 */ } int SqStackEmpty(SqStack S) {/* S为顺序栈 */ } int MatchBrackets(char a[], int n) { SqStack s; DataType x; int i; InitSqStack(&s); for ( i = 0 ; i < n ; i++ ) { if( S.top == -1 ) return 1; else SqStackPush( &s,a[i] return 0; if (a[i]=='(') else if( a[i]==')' return 0; /* 栈为空 */ if ( S->top == -1 ) *e = S->items[S->top]; S->top--; /* 修改栈顶指针 */ return 1; /* 将栈顶元素带回来 */ (2分)) (2分)); (2分)); (2分)) return 0; return 1; SqStackPop( &s,&x } if ( SqStackEmpty(s) else } int main() { printf("字符串中的小括号是成对的"); printf("字符串中的小括号不是成对的"); } char a[100]; int n = 0; int rst; gets(a); n = strlen(a) rst = MatchBrackets(a,n); if( rst == 1) return 0; (2分); else 5-2 本题目要求循环队列的元素入队、遍历和清空。保存 https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 作者单位通信DS课程组成都信息工程大学 2/16

2020/6/18 题目列表时间限制内存限制 400 ms 64 MB 解题报告 (2分) ); return ( (QUEUESIZE + Q.rear - Q.front) % QUEUESIZE (2分)) printf("队列已满，不能完成入队操作!\n"); return 0; if( (Q->rear+1)%QUEUESIZE==Q->front { } Q->items[Q->rear] = e; Q->rear = (Q->rear+1)% QUEUESIZE ;/* 重新设置队尾指针 */ return 1; (1分)) /*队列为空*/ printf("队列已空，不能完成出队操作!\n"); return 0; if( Q->rear == Q->front { } *e = Q->items[Q->front]; Q->front = (Q->front+1) % QUEUESIZE;/*重新设置队头指针*/ return 1; 剩余时间:3天 return 1 ; return 0 ; Q->front = 0; Q->rear = 0; return 1; DataType items[QUEUESIZE]; int front,rear; /* 队头、队尾指针 */ if ( Q.rear == Q.front ) else #include #include #include typedef int DataType; #define QUEUESIZE 100 /* 队列的最大长度 */ /* 循环队列的定义 */ typedef struct { }SqQueue; int InitSqQueue(SqQueue *Q) { } int SqQueueEmpty (SqQueue Q) {/* 判别队列Q是否为空;若为空返回真值，否则返回假值 */ } int SqQueueLength (SqQueue Q) {/* 返回队列中元素个数 */ } int EnSqQueue(SqQueue *Q,DataType e) {/* Q为顺序队列，e为待入队的元素 */ } int DeSqQueue(SqQueue *Q, DataType *e) {/* 删除队列的队头元素，用e返回其值 */ } int TraverseSqQueue(SqQueue Q) { } int main() { int pos; pos = Q.front; while ( ( pos + 1 ) % QUEUESIZE <= Q.rear ) { } printf("\n"); return 1; SqQueue Q; DataType x; char ch; InitSqQueue(&Q); do { }while ((ch=getchar())!='\n'); TraverseSqQueue(Q) while ( !SqQueueEmpty(Q) { } if (SqQueueEmpty(Q)) printf("%d ",Q.items[pos]); pos++; scanf("%d",&x); EnSqQueue( &Q,x DeSqQueue(&Q,&x); (2分)); (1分); (2分)) 保存 https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 3/16

作者单位时间限制内存限制通信DS课程组成都信息工程大学 400 ms 64 MB // 查找，注意 (1分)) (1分); (2分),sizeof(p->stu.name)); // 字符串赋值，注意两个参数填入时的中英文逗号 2020/6/18 } { } return 0; printf("循环队列Q已经为空"); 剩余时间:3天题目列表输入数据举例 45 89 65 21 35 74 90 12 输出数据举例 45 89 65 21 35 74 90 12 循环队列Q已经为空 5-3 本题目要求完成在学生信息单链表中查找指定姓名的学生成绩，并打印出姓名，成绩。 (2分))!=0 ) // 分数 // 学生信息 DataType stu; struct LNode* link; char name[10]; // 姓名 int score; #include #include #include typedef struct{ }DataType; typedef struct{ }LNode,*PNode,*LinkList; // 初始化单链表，head为单链表头指针，细节在此不表 int InitLinkList(LinkList *head)； // h为指向单链表的指针，pos为插入位置，从1开始，x为待插入数据元素，细节在此不表 int LinkListInsert(LinkList h, int pos, DataType x)； int Find(LinkList h, char* s, DataType *x) { PNode p = h->link; while (p && strcmp( s,p->stu.name 两个参数填入时的中英文逗号的区别 { p = p->link; } if ( !strcmp(s,p->stu.name) { memcpy( x->name,p->stu.name 的区别 x->score = p->stu.score return 1; } else { return 0; } } int main() { LinkList L; char chName[10]; int i,pos=1; DataType x; DataType a[5] = {{"Tom",90},{"Lily",87},{"May",92},{"Lucy",78},{"Tracy",76}}; InitLinkList(&L); for (i=0;i<5;i++) { LinkListInsert(L,pos++,a[i]); } gets(chName) if ( Find(L,chName,&x) == 1 { printf("%s,%d\n", x.name,x.score } else { printf("No record for %s",chName); } return 0; } (1分); (1分)) (2分)); // 注意两个参数填入时的中英文逗号的区别 https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 4/16 保存

作者单位时间限制内存限制通信DS课程组成都信息工程大学 400 ms 64 MB 解题报告剩余时间:3天题目列表 2020/6/18 输入举例 May 输出举例 May,92 5-4 有一个顺序表A，通过键盘向A表中输入数据元素，其长度通过键盘输入，完成顺序表A数据录入。要求实现A表中相同的数据元素删除（若表中有相同数据元素仅保留1个），完善算法。 ++ Lm->Length; #include #define DateLength 100 typedef int ElemType; typedef struct { ElemType items[DateLength]; int Length; } List ; void InitList ( List *L ); // 顺序表初始化，细节在此不表 void DispList(List L); // 遍历顺序表，细节在此不表 int InsertList ( ElemType x, int n, List *Lm) // 在指定位置n插入元素 { int i, j; j = Lm->Length; i = n-1; if ( i > j ){ printf ( "\nInsert Pos error!\n" ); return 0; } for ( i = j ; i > n ; i-- ) Lm->items[i] = Lm->items[i-1]; Lm->items[i] = x; return 0; } int DelList ( List *L, int n, ElemType *x ) // 删除指定位置n的元素 { int i, j; j = L->Length; i = n - 1; if (i > j) { printf ( "\nDel Pos error!\n" ); return 0; } *x = L->items[n - 1]; for ( i = n – 1 ; i < j – 1 ; i++ ) L->items[i]=L->items[i+1] L->Length -- return 1; } int main() { List A; int i, j, k; ElemType x; InitList ( &A ); scanf ( "%d", &j ); // 输入A表数据长度 for ( i = 0 ; i < j ; i++ ) // 输入A表数据 { } for ( i = 0 ; i < A.Length ; i++ ) return 1; } for ( j = i + 1 ; j < A.Length ; j++ ) if ( A.items[j] == A.items[i] ) scanf ( "%d", &k ); InsertList ( k,i+1,&A (4分) ; (1分); (3分)); DelList ( &A,j+1 (2分),&x); 5-5 本题目要求实现有序顺序表的二分查找，并输出待查找元素在顺序表中的数组下标。比如，顺序表A为{11 22 44 55 66 88 99 110 158 987}，查找A中88的位置，输出应为88所在的数组下标5。 https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 保存作者单位时间限制内存限制 CUIT通信DS课程组成都信息工程大学 400 ms 64 MB 5/16

2020/6/18 题目列表解题报告 /* 表示线性表的当前表长 */ (2分); 剩余时间:3天 DataType items[LISTSIZE]; /* 存放顺序表元素的数组 */ int length; #include #define LISTSIZE 100 /* LISTSIZE表示初始时，顺序表中最多含有LISTSIZE个元素 */ typedef int DataType; typedef struct { }SqList; int InitSqList(SqList *L)； // 初始化顺序表，细节在此不表 // 在顺序表第pos个元素前插入item元素，细节在此不表，pos从1开始 int SqListInsert( SqList *L, int pos, DataType item ) ; int BinarySearch(SqList L, DataType x) { /* L为静态查找表，x为待查找的数据元素 */ } int main() { } int low = 0, upper = L.length - 1, mid; while ( low <= upper ) { } return -1; SqList A; DataType x; char ch; int pos = 1,index = -1; InitSqList(&A); do { scanf("%d",&x); SqListInsert( &A,pos++,x }while ((ch=getchar())!='\n'); index = BinarySearch(A,88); printf("%d\n",pos); return 0; return mid mid= (low+upper)/2 if ( L.items[mid] == x ) if ( L.items[mid] < x ) else upper=mid-1 low=mid+1 (1分); (2分); (2分); (3分)); 5-6 有两个顺序表A、B，通过键盘向A、B表输入数据元素，在main函数里要求实现将B表中数据全部插入到A表中（将B表元素插入到A表尾部，结果存放于A表中）。作者单位时间限制内存限制通信DS课程组成都信息工程大学 400 ms 64 MB https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 6/16 保存

2020/6/18 题目列表剩余时间:3天 (3分); (2分); #include #define NumSize 100 typedef int ElemType; typedef struct { ElemType dat[NumSize]; int Length; } List; void InitList ( List *L ); // 顺序表初始化，细节在此不表 void DispList(List L); // 遍历顺序表，细节在此不表 int InsertList ( ElemType x, int n, List *Lm) // 在指定位置n插入元素 { int i, j; j = L->Length; i = n - 1; if ( i > j ) { printf( "\nInsert Pose Error!\n" ); return 0; } for ( i = j – 1 ; i > n – 1 ; i-- ) L->dat[i] = L->dat[i - 1]; L->dat[n-1]=x L->Length ++ return 1; } int main() { } List A, B;//B表中已存数据 int i, j, k; ElemType x; InitList ( &A ); InitList ( &B ); scanf ( "%d", &j ); // 输入A表长度 for ( i = 0 ; i < j ; i++ ) // 输入A表数据 { } scanf ( "%d", &j ); // 输入B表数据长度 for ( i = 0 ; i < j ; i++ ) // 输入B表数据 { } // 完成A、B两表简单合并算法 k = A.Length; for ( i = 0 ; i < B.Length ; i++ ) { } DispList(A); return 0; scanf ( "%d", &k ); InsertList ( &A, i+1, k ); scanf ( "%d", &k ); InsertList ( &B, i+1, k ); InsertList ( B.dat[i],++k,&A (3分) ); (2分) // 显示合并结果 5-7 本题目要求补充完整二叉树的创建和中序遍历算法。作者单位时间限制内存限制通信DS课程组成都信息工程大学 400 ms 64 MB 解题报告 https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 7/16 保存

2020/6/18 题目列表剩余时间:3天 DATATYPE data; // 数据域 struct Node *lchild; // 左孩子指针域 struct Node *rchild; // 右孩子指针域 #include #include #include #define N 100 typedef char DATATYPE; /****** 二叉树的二叉链表存储结构 ******/ typedef struct Node { }BTNode,*PBTNode,*BiTreeLink; /****** 创建二叉树 ******/ BiTreeLink CreateBinTree(char *nodes,int pos,int num) { PBTNode p; if(nodes[pos]==' '||pos>num) // 递归结束条件 return NULL; p = ( PBTNode if(!p) { printf("创建根结点失败！\n"); return 0; } p->data = nodes[pos] p->lchild=CreateBinTree(nodes,2*pos, num); // 建立左子树 p->rchild=CreateBinTree(nodes,2*pos+1, num); // 建立右子树 return p; } /****** 二叉树中序遍历 ******/ void inorder(BTNode *t) { (1分))malloc( sizeof(BTNode) if(t!=NULL) { (2分)); (2分); // 将数据存入数据域 inorder( t->lchild printf("%c ", t->data inorder(t->rchild); } int i; } void main() { BiTreeLink tree; } int length; char nodes[N],str[N]; gets(str); length = strlen(str); for (i = 0; i < length;i++) { } if (str[i] == ' ') { } else { } nodes[i+1] = '*'; nodes[i+1] = str[i]; (2分)); // 建立根结点 (2分)); // 获取用户输入序列 // 检查用户输入是否有空格 // 如有空格则用*代替 // 否则按照实际输入存储 tree = CreateBinTree( nodes // 创建二叉树 inorder(tree); // 中序遍历 (1分),1,length); 5-8 本题目要求利用栈的基本操作，实现一个清空顺序栈S的算法。作者单位时间限制内存限制通信DS课程组成都信息工程大学 400 ms 64 MB https://pintia.cn/problem-sets/1272511321327460352/problems/type/5 8/16 保存

资料库

PTA程序填空题14道.pdf

相关推荐

课程资源

热门标签

最新资料