\documentclass[11pt]{article} \usepackage{times} \usepackage{fancyheadings} \usepackage{alltt} \pagestyle{fancy} \usepackage{pifont} % for fancy bullets \newcommand{\headerfont}{\fontfamily{phv}\fontseries{b}\fontshape{n}% \fontsize{10}{12pt}\selectfont} \newcommand{\ttb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}% \fontsize{11}{13pt}\selectfont} \newcommand{\ttsb}{\fontfamily{pcr}\fontseries{b}\fontshape{n}% \fontsize{9}{11pt}\selectfont} \newcommand{\ttsi}{\fontfamily{pcr}\fontseries{m}\fontshape{it}% \fontsize{9}{11pt}\selectfont} \newcommand{\largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{14}{16pt}\selectfont} \newcommand{\Largebold}{\fontfamily{ptm}\fontseries{b}\fontshape{n}% \fontsize{19}{21pt}\selectfont} \newcommand{\Largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}% \fontsize{19}{21pt}\selectfont} \newcommand{\largeboldital}{\fontfamily{ptm}\fontseries{b}\fontshape{it}% \fontsize{14}{16pt}\selectfont} \newcommand{\mywidth}{6.0in} \newcommand{\st}{\rule[-.8mm]{0mm}{2mm}} \newcommand{\longst}{\rule[-3mm]{0mm}{2mm}} \newcommand{\outerbaselinesep}{12.5pt} \topmargin 0.0in \oddsidemargin 0.25in \evensidemargin 0.25in \textwidth \mywidth \textheight 8.7in \parindent 0mm %10mm \parskip 2.5mm \fboxrule=0.3mm %%%%%%%%% Headings %%%%%%%%%%%%%%%%%%%%%%% \setlength{\headwidth}{\textwidth} % This shouldn't be needed. ?? %\setlength{\headrulewidth}{0pt} % to eliminate rule under header \newcommand{\currhead}{CS 1723, Final Exam, \today} \lhead{\footnotesize \currhead} \rhead{\footnotesize Page \thepage~~of~~\pageref{'thatsall'}\hspace{0.4mm}} \lfoot{} \chead{} \cfoot{} \rfoot{} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \sloppy \begin{center} {\largebold CS 1723, Data Structures \\ Fall Semester, 1998} \\ {\largeboldital Final Examination} \end{center} %\baselineskip=\outerbaselinesep \begin{enumerate} %% 1 \item Give C code for the function {\ttb strlen} that will return the length of its character string input parameter. {\em Your function must not use brackets [].} ({\ttb strlen} is a C library function in {\ttb }). %% 2 \item \begin{enumerate} \item Regard the following array as a heap. Draw a tree diagram for this heap, and determine that the heap property fails at location 2. Show step-by-step how the heapify function will restore the heap property. (This example uses arrays based at 1, as we have done with examples in class.) {\footnotesize \begin{alltt} {\ttsb Array index:} 1 2 3 4 5 6 7 8 9 10 {\ttsb Array element:} 43 5 28 18 13 22 14 12 14 11 \end{alltt} } \item The following array satisfies the heap property. Show the first two steps of the heapsort algorithm. These steps should place two array elements in their proper locations and should restore the heap property for the remaining elements. Show the final result of these first two steps. {\footnotesize \begin{alltt} {\ttsb Array index:} 1 2 3 4 5 6 7 8 9 10 11 12 {\ttsb Array element:} 57 31 45 27 24 36 16 14 12 8 19 21 \end{alltt} } \end{enumerate} %% 3 \item Suppose we have a linked list of single characters, using the struct: \vspace{-0.1in} {\footnotesize \begin{verbatim} struct lnode { char data; struct lnode *next; }; \end{verbatim} } \vspace{-0.4in} \begin{enumerate} \item Write a function {\ttb listlength} that will find the length of this list by chasing down it and counting the nodes. {\ttb listlength} should return the length. Use the prototype: {\footnotesize \begin{verbatim} int listlength(struct lnode *list); \end{verbatim} } \vspace{-0.2in} \item Write a function {\ttb makelist} that will take an input character string and will create a linked list with each character of the string in a separate node of the list. (The nodes can be in backwards order.) The function should return a pointer to the start of the list.) You should use a prototype: {\footnotesize \begin{verbatim} struct lnode *makelist(char *s); \end{verbatim} } \end{enumerate} %%4 \item Recall that when C processes a command line, like say: {\ttb runner\% cc -o prog prog.c}, C sets up variables {\ttb argc} and {\ttb argv} as if they were initialized as follows: {\footnotesize \begin{verbatim} int argc = 4; char *argv[] = {"cc", "-o", "prog", "prog.c", NULL}; \end{verbatim} } By any method, give a loop that will print each string in the array {\ttb argv}, one to a line. %% 5 \item Consider the following portion of the binary tree program discussed in class. This tree is keeping a single character at each node. The {\ttb addtree} function will add nodes so that alphabetic order is the natural order of the tree. {\footnotesize \begin{alltt} {\ttsi #include #include #include #include struct tnode \{ char ch; struct tnode *left; struct tnode *right; \}; void addtree(struct tnode *, char ); struct tnode *newnode(char ); void treeprint(struct tnode *); struct tnode *lookup(struct tnode *, char ); void main(void) \{ struct tnode *root; struct tnode *p; char c; root = NULL; while ((c = getchar()) != '\(\backslash\)n') \{ if (root == NULL) root = newnode(c); else addtree(root, c); \} treeprint(root); printf("\(\backslash\)n"); p = lookup(root, 'x'); if (p == NULL) printf("Not found\(\backslash\)n"); else printf("Here it is: %c\(\backslash\)n", p -> ch); \} } runner% {\ttsb exam2_3 The quick brown fox jumps over the lazy dog.} .Tabcdefghijklmnopqrstuvwxyz Here it is: x runner% {\ttsb exam2_3 The quick brown pig jumps up in the air.} .Tabceghijkmnopqrstuw Not found \end{alltt} } \begin{enumerate} \item Supply code for a function {\ttb treeprint} that prints the nodes in alphabetic order. \item Supply code for a {\ttb lookup} function that will look up the character that is its second argument. If it finds the character, it returns a pointer to the node containing the character, and otherwise it returns {\ttb NULL}. ({\ttb lookup} is similar in logic to the {\ttb addtree} function, but simpler because there is no need to add a node.) \end{enumerate} \newpage %% 6 \item Write C code for a recursive binary search function. This function will look up an element {\ttb x} in a sorted array {\ttb a}. The function should use a divide-and-conquer strategy similar to quicksort. (This function does not use a binary tree, but just repeatedly divides the input array in half.) The function should have the following prototype: {\footnotesize \begin{verbatim} int bin_search(int a[M], int p, int r, int x); \end{verbatim} } {\ttb bin\_search} should search for the element {\ttb x} in the array {\ttb a}, in positions {\ttb a[p]}, ... , {\ttb a[r]}. The array {\ttb a} is assumed to be sorted into increasing order. The function should use the following strategy: check the array element in the middle between elements with index {\ttb p} and {\ttb r} --- call this middle index {\ttb q}. In case {\ttb x == a[q]}, return {\ttb q}. In case {\ttb x < a[q]}, let {\ttb bin\_search} work recursively on the positions from {\ttb p} to {\ttb q-1} and in case {\ttb x > a[q]}, let {\ttb bin\_search} work recursively on the positions from {\ttb q+1} to {\ttb r}. Your code must also decide how to terminate the recursion. In case {\ttb x} is not in the array, return {\ttb -1}. This {\ttb bin\_search} function might be called from a C main function as follows: {\footnotesize \begin{verbatim} int a[M]; /* obtain values for a[0], . . . , a[M-1] */ /* sort a[0], . . . , a[M-1] into increasing order */ /* obtain a value x to search for in the array a */ index = bin_search(a, 0, M-1, x); if (index == -1) printf("Element %d not present\n", x); else printf("Element %d present at location %d\n", x, index); \end{verbatim} } \end{enumerate} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \label{'thatsall'} \end{document}