数据结构课堂练习2012答案.docVIP

计算机科学与技术专业“数据结构”课堂练习（2012年） 学号 姓名 一、简答题（42分） 1． 将中缀表达式 a+[b-c*d^(e+f/g)] 改为后缀表达式。 abcdefg/+^*-+ 2． 写出模式‘abcabcdab’中各个字符的失败链接值。 模式字符 a b c a b c d a b Next[ ] -1 0 0 0 1 2 3 0 1 3． 一个线性表经常需要进行插入和删除操作，试问应选哪种存储方式？ 链表 4． 分析下列程序的时间复杂度： s=0; for (i=0;in;i++) for(j=0;jm;j++) s+=a[i][j]; O(nm) 5． 画出链式队列的示意图。 q front rear 6．两个字符串相等的充要条件是什么？ 串长度相等且对应字符相同 7． 将N阶上三角矩阵（数组）A[N][N] 压缩存储于一维数组B[ ]中，那么元素A[i][j]置于B[k]处，试写出i、j和k的关系式： k = 二、编程题（每题20分） 设有一个存放着n个字符的数组，试编函数judge( )，利用栈来判断这个字符串是否中心对称。若对称，则返回1；反之，则返回0 。 #define MAXN 100 char ch[MAXN]; int n; typedef struct { char data[MAXN]; int top; } SqStack; int judge(char ch[ ], int n) { SqStack *s; int i=0; s-top=-1; while(in) s-data[++s-top]=ch[i++]; i=0; while(ins-data[s-top]==ch[i])； { s-top--; i++; } if(i=n) return 1; else return 0; } 设一个带有表头结点的链表，链表的头指针为head，每个结点有两个字段：data和link，其中，指针link为链表的链接指针，整型字段data存放结点的键值。试编函数search(x)来查询键值等于x的结点。要求将查询到键值等于x的结点向表头方向移动一个位置（但不能移到表头结点的前面，即第一个结点不移动），并返回指向该结点的指针；若结点不存在，返回NULL。 typedef struct lnode { int data; struct lnode *link; } LinkList; LinkList *search (LinkList *head，int x) { LinkList *p, *q; p=NULL; q=head; while(q-link!=NULLq-link-data!=x) { p=q; q=q-link; } if(q-link==NULL) return NULL; if(p!=NULL) { p-link=q-link; q-link=q-link-link; p-link-link=q; return p-link; } return head-link; } 三、根据题意，将下列程序写完整（18分） 设稀疏矩阵A以行序为主序，顺序存储于数据结构为TSMatrix的三元组顺序表t中，现要求将A转置成B，即A的第i行成为B的第i列，B的非零元素仍以行序为主序，顺序存储于数据结构为TSMatrix的三元组顺序表中，新生成的三元组顺序表为tb。 #define MaxSize 100 typedef struct { int r; int c; float d; } TupNode; typedef struct { int rows; int cols; int nums TupNide data[MaxSize]; } TSMatrix; void TranTat(TSMatric t, TSMatrix tb) { int p, q=0, v; tb.rows=______(1)________; tb.cols=______(2)________; tb.nums=______(3)________; if(t.nu